Item Details

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
20121029
Published
University of Virginia, Department of Computer Science, 1999
Published Date
1999
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online