Finding optimal edge-rankings of trees

An edge-ranking of an undirected graph G is a labeling of the edges of G with integers such that every path between two edges with the same label i contains an edge with label j > i. An edge-ranking using a minimum number of ranks is called an optimal edge-ranking. The problem of finding an optimal edge-ranking of G has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding the minimum height edge separator tree of G. Polynomial-time algorithms for the problem on trees have been obtained, which find an optimal edge-ranking of a tree T in time O(n³ log n) where n is the number of vertices in T. In our previous paper we have given a simple O(n²) algorithm. This paper presents a more efficient algorithm, which finds an optimal edge-ranking of a tree in time O(n log n).