loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Sun-Yuan Hsieh, National Cheng Kung University, Taiwan
Huang-Ming Gao, National Cheng Kung University, Taiwan
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.