DocumentCode
479422
Title
Parallel Algorithms for Steiner Tree Problem
Author
Park, Joon-Sang ; Ro, Won W. ; Lee, Handuck ; Park, Neungsoo
Author_Institution
Hongik Univ., Seoul
Volume
1
fYear
2008
fDate
11-13 Nov. 2008
Firstpage
453
Lastpage
455
Abstract
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.
Keywords
parallel algorithms; trees (mathematics); 2-approximation algorithm; Berman algorithm; Steiner tree problem; parallel algorithms; parallel random access machine; Approximation algorithms; Biological system modeling; Cost function; Information technology; Joining processes; Parallel algorithms; Phylogeny; Routing; Tree graphs; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Convergence and Hybrid Information Technology, 2008. ICCIT '08. Third International Conference on
Conference_Location
Busan
Print_ISBN
978-0-7695-3407-7
Type
conf
DOI
10.1109/ICCIT.2008.167
Filename
4682068
Link To Document