𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Steiner trees in uniformly quasi-bipartite graphs

✍ Scribed by Clemens Gröpl; Stefan Hougardy; Till Nierhoff; Hans Jürgen Prömel

Book ID
104136745
Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
89 KB
Volume
83
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

The area of approximation algorithms for the Steiner tree problem in graphs has seen continuous progress over the last years. Currently the best approximation algorithm has a performance ratio of 1.550. This is still far away from 1.0074, the largest known lower bound on the achievable performance ratio. As all instances resulting from known lower bound reductions are uniformly quasi-bipartite, it is interesting whether this special case can be approximated better than the general case. We present an approximation algorithm with performance ratio 73/60 < 1.217 for the uniformly quasi-bipartite case. This improves on the previously known ratio of 1.279 of Robins and Zelikovsky. We use a new method of analysis that combines ideas from the greedy algorithm for set cover with a matroid-style exchange argument to model the connectivity constraint. As a consequence, we are able to provide a tight instance.

📜 SIMILAR VOLUMES

Constructing trees in bipartite graphs
Constructing trees in bipartite graphs
✍ U. Schulte 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 227 KB

In this paper we shall show that if G = (V,E) is a bipartite graph with more than (a -1)j YJ + (b -1)1X1 -(a -l)(b -1) edges, where (X, Y) is a vertex-partition for G and a < b are natural numbers with a < 1x1, b < 1 YI, then G contains every tree T with bipartitenumbers a < b. This result is relate

Two trees in maximal planar bipartite gr
Two trees in maximal planar bipartite graphs
✍ Gerhard Ringel 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract It is proven that each maximal planar bipartite graph is decomposable into two trees. © 1993 John Wiley & Sons, Inc.

Approximating Steiner trees in graphs wi
Approximating Steiner trees in graphs with restricted weights
✍ Halld�rsson, Magn�s M.; Ueno, Shuichi; Nakao, Hiroshi; Kajitani, Yoji 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 2 views

We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d °2. The improvement over other analyzed algorithms is a fac