An NC Parallel Algorithm for Generalized Vertex-Rankings of Partial k-Trees

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Abul Kashem Articles by Xiao Zhou Articles by Takao Nishizeki

1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97)

Taipei, Taiwan

December 18-December 20

ISBN: 0-8186-8259-0

	ASCII Text	x
	Abul Kashem, Xiao Zhou, Takao Nishizeki, "An NC Parallel Algorithm for Generalized Vertex-Rankings of Partial k-Trees," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 105, 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), 1997.

	BibTex	x
	@article{ 10.1109/ISPAN.1997.645078, author = {Abul Kashem and Xiao Zhou and Takao Nishizeki}, title = {An NC Parallel Algorithm for Generalized Vertex-Rankings of Partial k-Trees}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1997}, issn = {1087-4089}, pages = {105}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1997.645078}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - An NC Parallel Algorithm for Generalized Vertex-Rankings of Partial k-Trees SN - 1087-4089 SP EP A1 - Abul Kashem, A1 - Xiao Zhou, A1 - Takao Nishizeki, PY - 1997 KW - Parallel algorithm KW - Partial k-tree KW - Separator tree KW - Treewidth KW - Vertex-ranking VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Abul Kashem, Tohoku University, Sendai 980-77, Japan

Xiao Zhou, Tohoku University, Sendai 980-77, Japan

Takao Nishizeki, Tohoku University, Sendai 980-77, Japan

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1997.645078

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.

Index Terms:

Parallel algorithm, Partial k-tree, Separator tree, Treewidth, Vertex-ranking

Citation:

Abul Kashem, Xiao Zhou, Takao Nishizeki, "An NC Parallel Algorithm for Generalized Vertex-Rankings of Partial k-Trees," ispan, pp.105, 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), 1997

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.