APPROXIMATION ALGORITHMS FOR THE TERMINAL STEINER TREE PROBLEM

被引：0

作者：

Chen, Yen Hung ^{[1
]}

Lin, Ying Chin ^{[2
]}

机构：

[1] Univ Taipei, Dept Comp Sci, 1 Ai Guo West Rd, Taipei 10048, Taiwan

[2] Feng Chia Univ, Dept Appl Math, 100 Wenhwa Rd, Taichung 40724, Taiwan

来源：

APPLIED AND COMPUTATIONAL MATHEMATICS | 2018年 / 17卷 / 03期

关键词：

Approximation Algorithms; Approximation Scheme; Steiner Tree; Terminal Steiner Tree Problem; Network Communication; Evolutionary Tree Reconstruction In Biology; Telecommunications; NP-Complete; GRAPHS; RATIO; FULL;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given a complete graph G = (V, E) with a weight function on edges and a subset R of V, the terminal Steiner tree is a Steiner tree in G with all the vertices of R as its leaves. The terminal Steiner tree problem is concerned with the determination of a terminal Steiner tree with minimum weight. This paper shows an approximation scheme with performance ratio of (2 rho - (rho alpha-rho)/(rho alpha+rho+2 alpha-6) ) for the terminal Steiner tree problem, where p is the best-known performance ratio for the Steiner tree problem with any alpha >= 2.

引用

页码：246 / 255

页数：10

共 32 条

[1]

[Anonymous], 1996, CS9606 U VIRG

[2]

[Anonymous], TUTORIAL PHYLOGENETI

[3] IMPROVED APPROXIMATIONS FOR THE STEINER TREE PROBLEM [J].

BERMAN, P ;

RAMAIYER, V .

JOURNAL OF ALGORITHMS, 1994, 17 (03) :381-408

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

BERN, M ;

PLASSMANN, P .

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

[5] On full Steiner trees in unit disk graphs [J].

Biniaz, Ahmad ;

Maheshwari, Anil ;

Smid, Michiel .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2015, 48 (06) :453-458

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

Borchers, A ;

Du, DZ .

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

[7] Steiner Tree Approximation via Iterative Randomized Rounding [J].

Byrka, Jaroslaw ;

Grandoni, Fabrizio ;

Rothvoss, Thomas ;

Sanita, Laura .

JOURNAL OF THE ACM, 2013, 60 (01)

[8] On wirelength estimations for row-based placement [J].

Caldwell, AE ;

Kahng, AB ;

Mantik, S ;

Markov, IL ;

Zelikovsky, A .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1999, 18 (09) :1265-1278

[9]

Chen YH, 2011, LECT NOTES COMPUT SC, V6784, P141

[10]

Chen YH, 2003, LECT NOTES COMPUT SC, V2697, P122

← 1 2 3 4 →