An optimal parallel algorithm for c-vertex-ranking of trees

For a positive integer c, a c-vertex-ranking of a graph G = (V, E) is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels > i leaves connected components, each having at most c vertices with label i. The c-vertex-ranking problem is to find a c-vertex-ranking of a given graph using the minimum number of ranks. In this paper we give an optimal parallel algorithm for solving the c-vertex-ranking problem on trees in O (log(2) n) time using linear number of operations on the EREW PRAM model. (C) 2004 Elsevier B.V. All rights reserved.