On the complexity of finding optimal edge rankings

by Yue, Fung-ling

Abstract (Summary)
(Uncorrected OCR) 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.
Bibliographical Information:


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

© 2009 All Rights Reserved.