loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97)
An efficient parallel algorithm for the planar mincut linear arrangement problem for trees
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
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
Usage of this product signifies your acceptance of the Terms of Use.