Title Optimal edge ranking of trees in linear time
Tak Wah, Fung Ling · 1998
Finding an optimal node ranking and an edge ranking of a tree are interesting computational problems. The former problem already has a linear time algorithm in the literature. For the latter, only recently polynomial time algorithms have been revealed, and the best known algorithm takes O(n2 logn) time. In this paper, we present a new approach for finding an optimal edge ranking in O(n) time, showing that the optimal edge ranking problem is no more difficult than the node counterpart.