Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'06) Hardness and Approximation of the Selected-Leaf-Terminal Steiner Tree Problem Taipei, Taiwan December 04-December 07 ISBN: 0-7695-2736-1
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PDCAT.2006.68
For a complete graph G = (V,E) with length function l : E \to R^+ and two vertex subsets R \subset V and R' \subseteq 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 _{(uu,v) \in T} 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.
Citation:
Sun-Yuan Hsieh, Huang-Ming Gao, "Hardness and Approximation of the Selected-Leaf-Terminal Steiner Tree Problem," pdcat, pp.565-568, Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'06), 2006 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||