Optimal node ranking of trees

Ananth V. Iyer; H. Donald Ratliff; G. Vijayan

doi:10.1016/0020-0190(88)90194-9

Optimal node ranking of trees

Ananth V. Iyer
, H. Donald Ratliff
, G. Vijayan

MGT Dean's Office Administration

University at Buffalo

Research output: Contribution to journal › Article › peer-review

75 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	225-229
Number of pages	5
Journal	Information Processing Letters
Volume	28
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(88)90194-9
State	Published - Aug 12 1988

Keywords

Tree
algorithm
node separator
rank

Access to Document

10.1016/0020-0190(88)90194-9

Cite this

@article{15f8356081964a82bbf588a02e25e07a,

title = "Optimal node ranking of trees",

abstract = "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.",

keywords = "Tree, algorithm, node separator, rank",

author = "Iyer, \{Ananth V.\} and Ratliff, \{H. Donald\} and G. Vijayan",

year = "1988",

month = aug,

day = "12",

doi = "10.1016/0020-0190(88)90194-9",

language = "English",

volume = "28",

pages = "225--229",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Optimal node ranking of trees

AU - Iyer, Ananth V.

AU - Ratliff, H. Donald

AU - Vijayan, G.

PY - 1988/8/12

Y1 - 1988/8/12

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

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

KW - Tree

KW - algorithm

KW - node separator

KW - rank

UR - https://www.scopus.com/pages/publications/0024056258

U2 - 10.1016/0020-0190(88)90194-9

DO - 10.1016/0020-0190(88)90194-9

M3 - Article

SN - 0020-0190

VL - 28

SP - 225

EP - 229

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Optimal node ranking of trees

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this