Title :
Parallel Algorithms for Steiner Tree Problem
Author :
Park, Joon-Sang ; Ro, Won W. ; Lee, Handuck ; Park, Neungsoo
Author_Institution :
Hongik Univ., Seoul
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;
Conference_Titel :
Convergence and Hybrid Information Technology, 2008. ICCIT '08. Third International Conference on
Conference_Location :
Busan
Print_ISBN :
978-0-7695-3407-7
DOI :
10.1109/ICCIT.2008.167
