Optimal Edge Ranking of Trees in Polynomial Time.
Pilar de la Torre, Raymond Greenlaw, Alejandro A. Schäffer · 1993
An edge ranking of a graph is a labeling of the edges using positive integers such that all paths between two edges with the same label contain an intermediate edge with a higher label. An edge ranking is optimal if the highest label used is as small as possible. The edge-ranking problem has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding the minimum height edge-separator tree. In this paper we give the first polynomial-time algorithm to find an optimal edge ranking of a tree, placing the problem in P. An interesting feature of the algorithm is an unusual greedy procedure that allows us to narrow an exponential search space down to a polynomial search space containing an optimal solution. An NC algorithm is presented that finds an optimal edge ranking for trees of constant degree. We also prove that a natural decision problem emerging from our sequential algorithm is P-complete. Keywords: Edge ranking, minimum height edge-separator...