Item Details

Print View

Improved Steiner Tree Approximation in Graphs

Robins, Gabriel; Zelikovsky, Alexander
Format
Report
Author
Robins, Gabriel
Zelikovsky, Alexander
Abstract
The Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-time heuristic with an approximation ratio approaching 1 + 1~___33 ~ 1.55, which improves upon the previously best-known approximation algorithm of [10] with performance ratio ~ 1.59. In quasi-bipartite graphs (i.e., in graphs where all non-terminals are pairwise disjoint), our algorithm achieves an approximation ratio of ~ 1.28, whereas the previously best method achieves an approximation ratio approachiug 1.5 [19]. For complete graphs with edge weights 1 and 2, we show that our heuristic has an approximation ratio approaching ~ 1.28, which improves upon the previously best-known ratio of ~ 4 [4]. Our method is considerably simpler and easier to implement than previous approaches. Our techniques can also be used to prove that the Iterated 1-Steiner heuristic [14] achieves an approximation ratio of 1.5 in quasi-blpartite graphs, thus providing the first known non-trivial performance ratio of this well-known method. Note: Abstract extracted from PDF text
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 1999
Published Date
1999
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online