On the complexity of finding optimal edge rankings
Abstract of thesis entitled
?n the Complexity of Finding Optimal Edge Rankings?submitted by Yue Fung Ling
for the degree of Master of Philosophy
at the University of Hong Kong
in December 1996
In this thesis, we study the complexity of finding an optimal edge ranking of a graph. An edge ranking of an undirected 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 a label j > i. An edge ranking is optimal if it uses the least number of distinct labels among all possible edge rankings. The study of optimal edge rankings is initiated by Iyer, Ratliff and Vijayan, who found this problem has an interesting application in scheduling the assembly of multipart products.
In this work, we show that the edge ranking problem which, given a graph G and an integer t, determines whether G has an edge ranking using at most t distinct labels, is NP-complete, thus proving that the problem does not admit any polynomial time algorithm unless P = NP.
Finding an optimal edge ranking of a tree has a practical application in the assembly of multipart products. This problem has been studied quite intensively by a number of researchers. The best known algorithm is given by Zhou and Nishizeki and has running time O(n2 log ?) where n is the number of nodes in the tree and ? is the maximum degree. We improve their work with a number of novel ideas, and obtain the first O(n) time algorithm for finding an optimal edge ranking of a tree with n nodes.
We initiate a study on the best polynomial time approximation algorithm for the edge ranking problem of graphs. We present a non-approximability proof that no polynomial time algorithms can give a performance guarantee within an additive value of m^"e of the optimal for any constant ? > 0, where m is the number of edges in the graph. We also derive an approximation algorithm for finding an edge ranking of a graph with m edges using no more than clog2m times the number of distinct labels used by the optimal edge ranking for some constant c > 0.
School:The University of Hong Kong
School Location:China - Hong Kong SAR
Source Type:Master's Thesis
Keywords:trees graph theory computational complexity
Date of Publication:01/01/1997