Back to Search Start Over

Generalized vertex-rankings of trees

Authors :
Nobuaki Nagai
Xiao Zhou
Takao Nishizeki
Source :
Information Processing Letters. 56:321-328
Publication Year :
1995
Publisher :
Elsevier BV, 1995.

Abstract

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

Details

ISSN :
00200190
Volume :
56
Database :
OpenAIRE
Journal :
Information Processing Letters
Accession number :
edsair.doi...........04b332d1e760e912eee76a09ce0ad05e
Full Text :
https://doi.org/10.1016/0020-0190(95)00172-7