Optimal node ranking of tree in linear time.

*(English)*Zbl 0683.68038Summary: 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.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68P10 | Searching and sorting |

68R10 | Graph theory (including graph drawing) in computer science |

PDF
BibTeX
XML
Cite

\textit{A. A. Schäffer}, Inf. Process. Lett. 33, No. 2, 91--96 (1989; Zbl 0683.68038)

Full Text:
DOI

##### References:

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