標題: The full Steiner tree problem
作者: Lu, CL
Tang, CY
Lee, RCT
生物科技學系
Department of Biological Science and Technology
關鍵字: full Steiner tree problem;phylogenetic tree;evolutionary tree;NP-complete;MAX SNP-hard;approximation algorithm
公開日期: 5-Sep-2003
摘要: 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 subset of 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 I or 2. For the instances with lengths either I or 2, we give a 8/5-approximation algorithm to find an approximate solution for the problem. (C) 2003 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/S0304-3975(03)00209-3
http://hdl.handle.net/11536/27537
ISSN: 0304-3975
DOI: 10.1016/S0304-3975(03)00209-3
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 306
Issue: 1-3
起始頁: 55
結束頁: 67
Appears in Collections:Articles


Files in This Item:

  1. 000185261500004.pdf