Approximation algorithm for edge-ranking of series-parallel graphs

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.