Paper Info
Title
The full Steiner tree problem
Abstract
Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G=(V,E) with a length function on E and a proper subset R¿V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either 1 or 2. For the instances with lengths either 1 or 2, we give a 85-approximation algorithm to find an approximate solution for the problem.
Year
DOI
Venue
2003
10.1016/S0304-3975(03)00209-3
Theor. Comput. Sci.
Keywords
DocType
Volume
approximate solution,np-complete,proper subset r,length function,full steiner tree problem,phylogenetic tree,approximation algorithm,steiner tree,5-approximation algorithm,minimum length,evolutionary tree,full steiner tree,max snp-hard
Journal
306
Issue
ISSN
Citations 
1
Theoretical Computer Science
25
PageRank 
References 
Authors
1.11
6
3
Name
Order
Citations
PageRank
Chin Lung Lu142334.59
Chuan Yi Tang270479.25
Richard Chia-Tung Lee3422.90