TY - GEN
T1 - Parallel algorithms for steiner tree problem
AU - Park, Joon Sang
AU - Ro, Won W.
AU - Lee, Handuck
AU - Park, Neungsoo
PY - 2008
Y1 - 2008
N2 - The Steiner tree problem seeks for the shortest tree connecting a given set of terminal points. This paper discusses parallelization of algorithms for the Steiner tree problem. First, a 2-approximation algorithm due to Takahashi and Matsuyama is parallelized for PRAM(Parallel Random Access Machine) model, and then issues in parallelizing another 2-approximation heuristic, namely, Kou, Markowsky, and Berman algorithm and other advance heuristics achieving less approximation ratio are discussed.
AB - The Steiner tree problem seeks for the shortest tree connecting a given set of terminal points. This paper discusses parallelization of algorithms for the Steiner tree problem. First, a 2-approximation algorithm due to Takahashi and Matsuyama is parallelized for PRAM(Parallel Random Access Machine) model, and then issues in parallelizing another 2-approximation heuristic, namely, Kou, Markowsky, and Berman algorithm and other advance heuristics achieving less approximation ratio are discussed.
UR - http://www.scopus.com/inward/record.url?scp=57849133120&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57849133120&partnerID=8YFLogxK
U2 - 10.1109/ICCIT.2008.167
DO - 10.1109/ICCIT.2008.167
M3 - Conference contribution
AN - SCOPUS:57849133120
SN - 9780769534077
T3 - Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008
SP - 453
EP - 455
BT - Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008
T2 - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008
Y2 - 11 November 2008 through 13 November 2008
ER -