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||7|
|Publication status||Published - 1997|
|Event||3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 - Taipei, Taiwan, Province of China|
Duration: 1997 Dec 18 → 1997 Dec 20
|Conference||3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997|
|Country/Territory||Taiwan, Province of China|
|Period||97/12/18 → 97/12/20|