zbMATH — the first resource for mathematics

Optimal node ranking of tree in linear time. (English) Zbl 0683.68038
Summary: A. V. Iyer, H. D. Ratliff, and G. Vijayan [Inf. Process. Lett. 28, No.5, 225-229 (1988; Zbl 0661.68063)] define a ranking of an unrooted tree to be any mapping from the nodes of the tree to the set \(\{\) 1,2,...\(\}\) such that if two distinct nodes v, w have the same rank, then there exists a node x on the path between v and w such that the rank of x is greater than the rank of v and w. They also define a ranking to be optimal if the largest rank assigned to some node is as small as possible among all rankings. They give an O(n log n) time algorithm to find an optimal ranking of an n-node tree. This note describes an O(n) time algorithm to find an optimal ranking of a tree.

68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Iyer, A.V.; Ratliff, H.D.; Vijayan, G., Optimal node ranking of trees, Inform. process. lett., 28, 225-229, (1988) · Zbl 0661.68063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.