TY - GEN
T1 - Hardness and approximation of the selected-leaf-terminal steiner tree problem
AU - Hsieh, Sun-Yuan
AU - Gao, Huang Ming
PY - 2006/12/1
Y1 - 2006/12/1
N2 - For a complete graph G = (V, E) with length function l : E → R + and two vertex subsets R C V and R' C 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 Σ(v,v)εT(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.
AB - For a complete graph G = (V, E) with length function l : E → R + and two vertex subsets R C V and R' C 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 Σ(v,v)εT(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.
UR - http://www.scopus.com/inward/record.url?scp=38949172379&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38949172379&partnerID=8YFLogxK
U2 - 10.1109/PDCAT.2006.68
DO - 10.1109/PDCAT.2006.68
M3 - Conference contribution
AN - SCOPUS:38949172379
SN - 0769527361
SN - 9780769527369
T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings
SP - 565
EP - 568
BT - Proceedings - Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2006
T2 - 7th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2006
Y2 - 4 December 2006 through 7 December 2006
ER -