zbMATH — the first resource for mathematics

Edge ranking of trees. (English) Zbl 0862.05025
Summary: A \(k\)-edge ranking of an undirected graph is defined to be a labeling of the edges of the graph with set \(K=\{1,2, \dots, k\}\), such that all paths between two edges with the same label \(i\) contain an edge with label \(j>i\). Finding the smallest \(k\) for which a graph has a \(k\)-edge ranking is known as the edge ranking problem. An \(O(n \log n)\) time approximation algorithm for edge ranking of trees was developed by A. V. Iyer, H. D. Ratliff and G. Vijayan. In their paper [Discrete Appl. Math. 30, No. 1, 43-52 (1991; Zbl 0727.05053)] they mention that whether the problem of finding edge ranking of a tree is NP-hard is still an open question. In this paper, we resolve this question by developing a polynomial algorithm for finding edge ranking of a tree. The problem of edge ranking of a tree is solved by transforming the problem into an equivalent node ranking problem. The main result in the paper is an \(O(r^3)\) time algorithm for edge ranking of trees, where \(r\leq n\) is the edge rank number of the tree and \(n\) is the number of vertices of the tree.

05C05 Trees
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C85 Graph algorithms (graph-theoretic aspects)