An efficient parallel algorithm for the planar mincut linear arrangement problem for 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 Sung Kwon Kim

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
	Sung Kwon Kim, "An efficient parallel algorithm for the planar mincut linear arrangement problem for trees," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 240, 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), 1997.

	BibTex	x
	@article{ 10.1109/ISPAN.1997.645103, author = {Sung Kwon Kim}, title = {An efficient parallel algorithm for the planar mincut linear arrangement problem for trees}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1997}, issn = {1087-4089}, pages = {240}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1997.645103}, 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 efficient parallel algorithm for the planar mincut linear arrangement problem for trees SN - 1087-4089 SP EP A1 - Sung Kwon Kim, PY - 1997 KW - trees (mathematics); parallel algorithm; planar mincut; NP-complete; polynomial-time solvable; EREW PRAM VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Sung Kwon Kim, Dept. of Comput. Sci. & Eng., Chung-Ang Univ., Seoul, South Korea

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

The MINCUT problem for graphs is to find a linear arrangement with minimum cut. The problem is NP-complete for general graphs while polynomial-time solvable for trees. The PLANAR MINCUT problem does not allow edge crossings in arrangements. We present a parallel algorithm for the PLANAR MINCUT problem for trees with n vertices, which takes O(log/sup 2/ n) time and O(n) processors in the EREW PRAM.

Index Terms:

trees (mathematics); parallel algorithm; planar mincut; NP-complete; polynomial-time solvable; EREW PRAM

Citation:

Sung Kwon Kim, "An efficient parallel algorithm for the planar mincut linear arrangement problem for trees," ispan, pp.240, 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.