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

Ahmed Sh. Arefin

ISBN 10: 3639196848 / ISBN 13: 9783639196849

Edité par VDM Verlag Dr. Müller, 2009

Minimum Edge-Ranking Spanning Tree Problem of Series-Parallel Graphs | Finding NP Completeness, Efficient Approximation Algorithm and the Ratio | Ahmed Sh. Arefin | Taschenbuch | Englisch | VDM Verlag Dr. Müller | EAN 9783639196849 | Verantwortliche Person für die EU: preigu GmbH & Co. KG, Lengericher Landstr. 19, 49078 Osnabrück, mail[at]preigu[dot]de | Anbieter: preigu. N° de réf. du vendeur 101491925

Synopsis :

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.

Présentation de l'éditeur: 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.

Détails bibliographiques

Titre : Minimum Edge-Ranking Spanning Tree Problem ...
Éditeur : VDM Verlag Dr. Müller
Date d'édition : 2009
Reliure : Taschenbuch
Etat : Neu