ALCOMFT-TR-02-34

Tobias Polzin and Siavash Vahdati Daneshmand
On Steiner Trees and Minimum Spanning Trees in Hypergraphs
MPI. Work packages 2 and 5. May 2002.

Abstract: The bottleneck of the state-of-the-art algorithms for geometric Steiner problems is the concatenation-phase, where the hitherto most successful approach treats the generated full Steiner trees as edges of a hypergraph and uses an LP-relaxation of the minimum spanning tree in hypergraph (MSTH) problem. We study this original and some new equivalent relaxations of this problem and clarify their relations to all classical relaxations of the Steiner problem. In an experimental study, an algorithm of ours which is designed for general graphs turns out to be superior to the MSTH-approach.

Postscript file: ALCOMFT-TR-02-34.ps.gz (115 kb).