Algorithms for terminal Steiner trees

被引：21

作者：

Martinez, Fabio Viduani ^{[1
]}

de Pina, Jose Coelho ^{[2
]}

Soares, Jose ^{[2
]}

机构：

[1] Univ Fed Mato Grosso do Sul, Ctr Ciencias Exatas & Tecnol, Dept Computacao & Estatist, Campo Grande, MS, Brazil

[2] Univ Sao Paulo, Inst Matemat & Estatist, Dept Ciencia Computacao, Sao Paulo, SP, Brazil

来源：

THEORETICAL COMPUTER SCIENCE | 2007年 / 389卷 / 1-2期

基金：

巴西圣保罗研究基金会;

关键词：

terminal Steiner trees; approximation algorithms;

D O I：

10.1016/j.tcs.2007.08.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The terminal Steiner tree problem (TST) consists of finding a minimum cost Steiner tree where each terminal is a leaf. We describe a factor 2 rho - rho/(3 rho - 2) approximation algorithm for the TST, where rho is the approximation factor of a given algorithm for the Steiner tree problem. Considering the current best value of rho, this improves a previous 3.10 factor to 2.52. For the TST restricted to instances where all edge costs are either 1 or 2, we improve the approximation factor from 1.60 to 1.42. (c) 2007 Elsevier B.V All rights reserved.

引用

页码：133 / 142

页数：10

共 7 条

[1]

[Anonymous], 1989, SIAM J DISCRETE MATH, DOI DOI 10.1137/0402008

[2]

CHEN YH, 2003, 9 INT COMP COMB C CO, P122

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