Optimal edge ranking of trees in linear time
Tak‐Wah Lam, Fung Ling Yue · 1998
. Given a tree, finding an optimal node ranking and finding an optimal edge ranking 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 requires more than quadratic time. In this paper we present a new approach for finding an optimal edge ranking of a tree, improving the time complexity to linear. 1 Introduction Let G be an undirected graph. A node ranking of G is a labeling of its nodes with positive integers such that every path between two nodes with the same label i contains an intermediate node with label j ? i. A node ranking is optimal if it uses the least number of distinct labels among all possible node rankings. An edge ranking of G is a labeling of its edges satisfying an analogous condition, i.e., every path between two edges with the same label i contains an intermediate edge with label j ? i. Figure...