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 条

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

Borchers, A ;

Du, DZ .

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

[2]

Cheng X., 2001, Steiner trees in Industry

[3] On approximation algorithms for the terminal Steiner tree problem [J].

Drake, DE ;

Hougardy, S .

INFORMATION PROCESSING LETTERS, 2004, 89 (01) :15-18

[4]

Du D.Z., 2000, ADV STEINER TREE

[5] ON COMPONENT-SIZE BOUNDED STEINER TREES [J].

DU, DZ .

DISCRETE APPLIED MATHEMATICS, 1995, 60 (1-3) :131-140

[6]

Foulds L.R., 1982, Advances in Applied Mathematics, V3, P43, DOI [10.1016/S0196-8858(82)80004-3, DOI 10.1016/S0196-8858(82)80004-3]

[7] A note on the terminal Steiner tree problem [J].

Fuchs, B .

INFORMATION PROCESSING LETTERS, 2003, 87 (04) :219-220

[8]

GAREY M, 1997, SIAM J APPL MATH, V32, P835

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

GAREY, MR ;

JOHNSON, DS .

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

[10]

Graur D, 2000, Fundamentals in molecular evolution, V2nd

← 1 2 →