Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


On Steiner trees and minimum spanning trees in hypergraphs

Polzin, Tobias and Vahdati, Siavash

MPI-I-2001-1-005. December 2001, 15 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
The state-of-the-art algorithms for geometric Steiner
problems use a two-phase approach based on full Steiner trees
(FSTs). The bottleneck of this approach is the second phase (FST
concatenation phase), in which an optimum Steiner tree is constructed
out of the FSTs generated in the first phase. The hitherto most
successful algorithm for this phase considers the FSTs as edges
of a hypergraph and is based on an LP-relaxation of the minimum spanning
tree in hypergraph (MSTH) problem. In this paper, we compare this
original and some new relaxations of this problem and show their
equivalence, and thereby refute a conjecture in the literature.
Since the second phase can also be formulated as a Steiner
problem in graphs, we clarify the relation of this MSTH-relaxation to
all classical relaxations of the Steiner problem.
Finally, we perform some experiments, both on the quality of the
relaxations and on FST-concatenation methods based on them,
leading to the surprising result that an algorithm of ours
which is designed for general
graphs is superior to the MSTH-approach.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2000-1-005.pdfMPI-I-2001-1-005.ps288 KBytes; 143 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Polzin, Tobias and Vahdati, Siavash},
  TITLE = {On Steiner trees and minimum spanning trees in hypergraphs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2001-1-005},
  MONTH = {December},
  YEAR = {2001},
  ISSN = {0946-011X},