The full Steiner tree problem

被引：42

作者：

Lu, CL

Tang, CY ^{[1
]}

Lee, RCT

机构：

[1] Natl Tsing Hua Univ, Dept Comp Sci, Hsinchu 300, Taiwan

[2] Natl Chiao Tung Univ, Dept Biol Sci & Technol, Hsinchu 300, Taiwan

[3] Natl Chi Nan Univ, Dept Comp Sci & Informat Engn, Puli, Nantou Hsien, Taiwan

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 306卷 / 1-3期

关键词：

full Steiner tree problem; phylogenetic tree; evolutionary tree; NP-complete; MAX SNP-hard; approximation algorithm;

D O I：

10.1016/S0304-3975(03)00209-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：55 / 67

页数：13

共 20 条

[1]

[Anonymous], TUTORIAL PHYLOGENETI

[2]

[Anonymous], 2000, ADV STEINER TREES

[3] Proof verification and the hardness of approximation problems [J].

Arora, S ;

Lund, C ;

Motwani, R ;

Sudan, M ;

Szegedy, M .

JOURNAL OF THE ACM, 1998, 45 (03) :501-555

[4]

Ausiello G, 1999, COMPLEXITY APPROXIMA, DOI DOI 10.1007/978-3-642-58412-1

[5] THE STEINER PROBLEM WITH EDGE LENGTH-1 AND LENGTH-2 [J].

BERN, M ;

PLASSMANN, P .

INFORMATION PROCESSING LETTERS, 1989, 32 (04) :171-176

[6] The k-Steiner ratio in graphs [J].

Borchers, A ;

Du, DZ .

SIAM JOURNAL ON COMPUTING, 1997, 26 (03) :857-869

[7]

Cheng X., 2001, STEINER TREES IND

[8]

Foulds L.R., 1982, ADV APPL MATH, V3, P43, DOI DOI 10.1016/S0196-8858(82)80004-3

[9] COMPLEXITY OF COMPUTING STEINER MINIMAL TREES [J].

GAREY, MR ;

GRAHAM, RL ;

JOHNSON, DS .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :835-859

[10] RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :826-834

← 1 2 →