Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, G. Optimal node ranking of trees. (English) Zbl 0661.68063 Inf. Process. Lett. 28, No. 5, 225-229 (1988). We discuss the problem of ranking nodes of a tree, which is a restriction of the general node coloring problem. A tree is said to have rank number k if its vertices can be ranked using the integers 1,2,...,k such that if two nodes have the same rank i, then there is a node with rank greater than i on the path between the two nodes. The optimal rank number of a tree gives the minimum height of its node separator tree. We present an O(n log n) algorithm for optimal node ranking of trees. Cited in 1 ReviewCited in 40 Documents MSC: 68P10 Searching and sorting 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science Keywords:node coloring; node separator; node ranking of trees PDF BibTeX XML Cite \textit{A. V. Iyer} et al., Inf. Process. Lett. 28, No. 5, 225--229 (1988; Zbl 0661.68063) Full Text: DOI OpenURL References: [1] Iyer, A.V.; Ratliff, H.D.; Vijayan, G., Analysis of parallelism in assembly operations, () [2] Leiserson, C.E., Area-efficient graph layouts (for VLSI), Proc. 21st ann. IEEE symp. on foundations of computer science, 270-281, (1980) [3] Lewis, P.M.; Stearns, R.E.; Hartmanis, J., Memory bounds for recognition of context-free and context-sensitive languages, Proc. 6th ann. symp. on switching theory and logic design, 191-202, (1965) 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.