TY - JOUR

T1 - Generalized vertex-rankings of trees

AU - Zhou, Xiao

AU - Nagai, Nobuaki

AU - Nishizeki, Takao

PY - 1995/12/22

Y1 - 1995/12/22

N2 - We newly define a generalized vertex-ranking of a graph G as follows: for a positive integer c, a c-vertex-ranking of G is a labeling (ranking) of the vertices of G with integers such that, for any label i, every connected component of the graph obtained from G by deleting the vertices with label > i has at most c vertices with label i. Clearly an ordinary vertex-ranking is a l-vertex-ranking and vice-versa. We present an algorithm to find a c-vertex-ranking of a given tree T using the minimum number of ranks in time O(cn) where n is the number of vertices in T.

AB - We newly define a generalized vertex-ranking of a graph G as follows: for a positive integer c, a c-vertex-ranking of G is a labeling (ranking) of the vertices of G with integers such that, for any label i, every connected component of the graph obtained from G by deleting the vertices with label > i has at most c vertices with label i. Clearly an ordinary vertex-ranking is a l-vertex-ranking and vice-versa. We present an algorithm to find a c-vertex-ranking of a given tree T using the minimum number of ranks in time O(cn) where n is the number of vertices in T.

KW - Algorithms

KW - Generalized ranking

KW - Graphs

KW - Lexicographical order

KW - Trees

KW - Visible vertices

UR - http://www.scopus.com/inward/record.url?scp=0348105524&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0348105524&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(95)00172-7

DO - 10.1016/0020-0190(95)00172-7

M3 - Article

AN - SCOPUS:0348105524

SN - 0020-0190

VL - 56

SP - 321

EP - 328

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -