A c-vertex-ranking of a graph G for a positive integer c 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. We present a parallel algorithm to find a c-vertex-ranking of a partial k-tree using the minimum number of ranks. This is the first parallel algorithm for c-vertex-ranking of a partial k-tree G, and takes O(log n) time using a polynomial number of processors on the common CRCW PRAM for any positive integer c and any fixed integer k, where n is the number of vertices in G.
|Number of pages
|Published - 1997
|3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 - Taipei, Taiwan, Province of China
Duration: 1997 Dec 18 → 1997 Dec 20
|3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997
|Taiwan, Province of China
|97/12/18 → 97/12/20