Abstract:
This thesis deals with an approximation algorithm for finding edge-rankings
of 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.
Analogously, the vertex-ranking problem can be defined. The edge-ranking problem
of graphs has important applications like scheduling the parallel assembly of a
complex multi-part product from its components and parallel computation. The
edge-ranking problem is NP-complete for series-parallel graphs, that is, finding a
polynomial-time algorithm for solving the edge-ranking problem on series-parallel
graphs with unbounded maximum degree is unlikely. In this thesis, we present a
linear-time algorithm for finding a 2-vertex-separator tree of a series-parallel graph
G and a linear-time approximation algorithm for finding the edge-ranking of a given
series-parallel graph G using the 2-vertex-separator tree of G. Obtaining t.he 2-
vertex-separator tree of G immediately improves the running time of the known
best algorithm t.hat finds an optimal vertex-ranking of a series-parallel graph.
