Minimum Edge-Ranking Spanning Tree Problem of Series-Parallel Graphs: Finding NP Completeness, Efficient Approximation Algorithm and the Ratio - Brossura

Arefin, Ahmed Shamsul

 
9783639196849: Minimum Edge-Ranking Spanning Tree Problem of Series-Parallel Graphs: Finding NP Completeness, Efficient Approximation Algorithm and the Ratio
Brossura
ISBN 10: 3639196848 ISBN 13: 9783639196849
Casa editrice: VDM Verlag, 2009

Sinossi

This Book deals with the NP-Completeness and an approximation algorithm for finding minimum edge ranking spanning tree (MERST) on series-parallel graphs. An edge-ranking is optimal if the least number of distinct labels among all possible edge-rankings are used by it. The edge-ranking problem is to find an optimal edge-ranking of a given graph. The minimum edge-ranking spanning tree problem is to find a spanning tree of a graph G whose edge-ranking is minimum. The minimum edge-ranking spanning tree problem of graphs has important applications like scheduling the parallel assembly of a complex multi-part product from its components and relational database. Although polynomial-time algorithm to solve the minimum edge-ranking spanning tree problem on series- parallel graphs with bounded degrees has been found, but for the unbounded degrees no polynomial-time algorithm is known. In this work, we have proved that the minimum edge-ranking spanning tree problem for general series-parallel graph is NP-Complete and designed an efficient approximation algorithm which will find a near-optimal solution of the problem.

Le informazioni nella sezione "Riassunto" possono far riferimento a edizioni diverse di questo titolo.

L'autore

Ahmed Shamsul Arefin is a PhD candidate, Computer Science at The University of Newcastle, Australia. He is currently working at the Centre for Bioinformatics, Biomarker Discovery and Information-Based Medicine. His interests centre on large scale graph algorithmics and bioinformatics. He has recieved MSc. from BUET and BSc. from CUET, Bangladesh.

Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.

Editore
VDM Verlag
Data di pubblicazione
2009
Lingua
Inglese
ISBN 10 
3639196848
ISBN 13 
9783639196849
Rilegatura
Copertina flessibile
Numero di pagine
72
Contatto del produttore
non disponibile
Persona responsabile
non disponibile