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.

## Abstract

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