Optimal node ranking of trees
type: Item
instance of: scholarly article
title: Optimal node ranking of trees
zbMATH Open document ID: 0661.68063
DOI: 10.1016/0020-0190(88)90194-9
author: Ananth Iyer
author: H. Donald Ratliff
author: Gopalakrishnan Vijayan
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4080932
zbMATH Keywords: node coloring
zbMATH Keywords: node separator
zbMATH Keywords: node ranking of trees
Wikidata QID: Q56763504
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90194-9
OpenAlex ID: W2082764577
cites work: Q5180413
DBLP publication ID: journals/ipl/IyerRV88
description: scientific article; zbMATH DE number 4080932