A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree

被引：8

作者：

Li, Xianyue ^{[1
]}

Zou, Feng ^{[2
]}

Huang, Yaochun ^{[2
]}

Kim, Donghyun ^{[2
]}

Wu, Weili ^{[2
]}

机构：

[1] Lanzhou Univ, Sch Math & Stat, Lanzhou 730000, Gansu, Peoples R China

[2] Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA

来源：

ALGORITHMICA | 2010年 / 56卷 / 03期

关键词：

Selected-internal Steiner tree; Approximation algorithm; ALGORITHMS;

D O I：

10.1007/s00453-009-9301-8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R (') aSS RaS dagger V with |R-R (')|a parts per thousand yen2, selected-internal Steiner minimum tree problem is to find a minimum subtree T of G interconnecting R such that any leaf of T does not belong to R ('). In this paper, suppose c is metric, we obtain a (1+rho)-approximation algorithm for this problem, where rho is the best-known approximation ratio for the Steiner minimum tree problem.

引用

页码：333 / 341

页数：9

共 19 条

[11] Approximating the selected-internal Steiner tree [J].

Hsieh, Sun-Yuan ;

Yang, Shih-Cheng .

THEORETICAL COMPUTER SCIENCE, 2007, 381 (1-3) :288-291

[12] On the partial terminal Steiner tree problem [J].

Hsieh, Sun-Yuan ;

Gao, Huang-Ming .

JOURNAL OF SUPERCOMPUTING, 2007, 41 (01) :41-52

[13]

HWANG F. K., 1992, The Steiner tree problem, V53

[14]

Kahng A.B., 1995, OPTIMAL INTERCONNECT

[15]

Korte Bernhard, 1990, Paths, flows, and VLSI-layout

[16] On the terminal Steiner tree problem [J].

Lin, GH ;

Xue, GL .

INFORMATION PROCESSING LETTERS, 2002, 84 (02) :103-107

[17] The full Steiner tree problem [J].

Lu, CL ;

Tang, CY ;

Lee, RCT .

THEORETICAL COMPUTER SCIENCE, 2003, 306 (1-3) :55-67

[18] Algorithms for terminal Steiner trees [J].

Martinez, Fabio Viduani ;

de Pina, Jose Coelho ;

Soares, Jose .

THEORETICAL COMPUTER SCIENCE, 2007, 389 (1-2) :133-142

[19]

Robins G, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P770

← 1 2 →