Algorithms for generalized vertex-rankings of partial k-trees

A c-vertex-ranking of a graph G for a positive integer c is a labeling of t he 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. A c-vertex-ranking is optimal if the number of labe ls used is as small as possible. We present sequential and parallel algorit hms to find an optimal c-vertex-ranking of a partial k-tree, that is, a gra ph of treewidth bounded by a fixed integer fi. The sequential algorithm tak es polynomial-time for any positive integer c. The parallel algorithm takes O(log n) parallel time using a polynomial number of processors on the comm on CRCW PRAM, where n is the number of vertices in G. (C) 2000 Elsevier Sci ence B.V. All rights reserved.