An NC parallel algorithm for generalized vertex-rankings of partial k-trees

M. A. Kashem; Xiao Zhou; T. Nishizeki

doi:10.1109/ISPAN.1997.645078

An NC parallel algorithm for generalized vertex-rankings of partial k-trees

M. A. Kashem, Xiao Zhou, T. Nishizeki

INF - System Information Sciences

Tohoku University

Research output: Contribution to conference › Paper › peer-review

1 Citation (Scopus)

Abstract

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.

Original language	English
Pages	105-111
Number of pages	7
DOIs	https://doi.org/10.1109/ISPAN.1997.645078
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

Conference	3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997
Country/Territory	Taiwan, Province of China
City	Taipei
Period	97/12/18 → 97/12/20

Access to Document

10.1109/ISPAN.1997.645078

Cite this

@conference{65da836a031f4a50b8d86158ad42e74f,

title = "An NC parallel algorithm for generalized vertex-rankings of partial k-trees",

abstract = "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.",

author = "Kashem, {M. A.} and Xiao Zhou and T. Nishizeki",

note = "Publisher Copyright: {\textcopyright} 1997 IEEE.; 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 ; Conference date: 18-12-1997 Through 20-12-1997",

year = "1997",

doi = "10.1109/ISPAN.1997.645078",

language = "English",

pages = "105--111",

}

TY - CONF

T1 - An NC parallel algorithm for generalized vertex-rankings of partial k-trees

AU - Kashem, M. A.

AU - Zhou, Xiao

AU - Nishizeki, T.

PY - 1997

Y1 - 1997

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

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

UR - http://www.scopus.com/inward/record.url?scp=85037514507&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85037514507&partnerID=8YFLogxK

U2 - 10.1109/ISPAN.1997.645078

DO - 10.1109/ISPAN.1997.645078

M3 - Paper

AN - SCOPUS:85037514507

SP - 105

EP - 111

T2 - 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997

Y2 - 18 December 1997 through 20 December 1997

ER -

An NC parallel algorithm for generalized vertex-rankings of partial k-trees

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this