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 -