Minimum Edge-Ranking Spanning Tree Problem of Series-Parallel Graphs

Minimum Edge-Ranking Spanning Tree Problem of Series-Parallel Graphs  by Ahmed Shamsul Arefin, VDM Verlag Dr. Müller Aktiengesellschaft & Co. KG, Germany, 2009 ISBN- 978-3-639-19684-9

Top Tip : Make sure you have a high level anti virus software like Kaspersky installed on your pcs and mac computers to prevent any nasty surprises, see our Kaspersky deals page for more

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.

Leave a Reply

Your email address will not be published. Required fields are marked *