# 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.

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