Title :
Hardness and Approximation of the Selected-Leaf-Terminal Steiner Tree Problem
Author :
Hsieh, Sun-Yuan ; Gao, Huang-Ming
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Cheng Kung Univ., Tainan
Abstract :
For a complete graph G = (V, E) with length function l : E rarr R+ and two vertex subsets R sub V and R´ sube R, a selected-leaf-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R R´ belong to the leaves of this Steiner tree. The selected-leaf-terminal Steiner tree problem is to find a selected-leaf-terminal Steiner tree T whose total lengths Sigma (u, v)epsiT l(u, v) is minimum. In this paper, we show that the problem is both NP-complete and MAX SNP-hard when the lengths of edges are restricted to either 1 or 2. We also provide an approximation algorithm for the problem
Keywords :
approximation theory; computational complexity; trees (mathematics); MAX SNP-hard; NP-complete; approximation algorithm; complete graph; selected-leaf-terminal Steiner tree problem; Approximation algorithms; Computer science; Euclidean distance; Steiner trees; Terminology; Tree graphs;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2006. PDCAT '06. Seventh International Conference on
Conference_Location :
Taipei
Print_ISBN :
0-7695-2736-1
DOI :
10.1109/PDCAT.2006.68