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.
