Repository: Freie Universität Berlin, Math Department

Steiner trees in uniformly quasi-bipartite graphs

Gröpl, C. and Hougardy, S. and Nierhoff, T. and Prömel, H.-J. (2002) Steiner trees in uniformly quasi-bipartite graphs. Information Processing Letters, 83 . pp. 195-200.

Full text not available from this repository.


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.

Item Type:Article
Uncontrolled Keywords:Steiner trees, Graph algorithms, Approximation algorithms
Subjects:Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:354
Deposited By: Admin Administrator
Deposited On:14 Apr 2009 14:39
Last Modified:14 Apr 2009 14:39

Repository Staff Only: item control page