Minimum Edge-Ranking Spanning Tree Problem Of Series-Parallel Graphs: Finding Np Completeness, Efficient Approximation Algorithm And The Ratio

Arefin, Ahmed Sh.; Arefin, Ahmed Sh.

ISBN 10: 3639196848 / ISBN 13: 9783639196849

Published by Vdm Verlag Dr. Müller, 2009

About this Item

72 pages. 8.66x5.91x0.17 inches. In Stock.

Seller Inventory # 3639196848

Bibliographic Details

• Title: Minimum Edge-Ranking Spanning Tree Problem Of Series-Parallel Graphs: Finding Np Completeness, Efficient Approximation Algorithm And The Ratio
• Publisher: Vdm Verlag Dr. Müller
• Publication Date: 2009
• Language: English
• ISBN 10: 3639196848
• ISBN 13: 9783639196849
• Binding: Paperback
• Condition: Brand New

About this title

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.

About the Author

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.