On the minimum edge-ranking spanning tree problem of series parallel graphs

Abstract

This thesis deals with the NP-Completeness and an approximation algorithm for finding minimum edge ranking spanning tree (MERST) on series-parallel graphs. An edge-ranking of a graph G is a labeling of its edges with positive integers such that every path between two edges with the same label i contains an intermediate edge with label j > i. 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 multipart product from its components and relational database. Although polynomialtime algorithm to solve the minimum edge-ranking spanning tree problem on seriesparallel graphs with bounded degrees has been found, but for the unbounded degrees no polynomial-time algorithm is known. In this paper, 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.