APPROXIMATING STEINER TREES IN GRAPHS WITH RESTRICTED WEIGHTS

Authors
HALLDORSSON MM UENO S NAKAO H KAJITANI Y
Citation
Mm. Halldorsson et al., APPROXIMATING STEINER TREES IN GRAPHS WITH RESTRICTED WEIGHTS, Networks, 31(4), 1998, pp. 283-292
Citations number
10
Categorie Soggetti
Computer Science Hardware & Architecture","Computer Science Hardware & Architecture
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
31
Issue
4
Year of publication
1998
Pages
283 - 292
Database
ISI
SICI code
0028-3045(1998)31:4<283:ASTIGW>2.0.ZU;2-R
Abstract
We analyze the approximation ratio of the average distance heuristic f or the Steiner tree problem on graphs and prove nearly tight bounds fo r the cases of complete graphs with binary weights {1, d} or weights i n the interval [1, d], where d less than or equal to 2. The improvemen t over other analyzed algorithms is a factor of about e approximate to 2.718, (C) 1998 John Wiley & Sons, Inc. Networks 31. 283-292, 1998.