MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


On Steiner trees and minimum spanning trees in hypergraphs

Polzin, Tobias and Vahdati, Siavash

December 2001, 15 pages.

Status: available - back from printing

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.

  • Attachement: (288 KBytes); MPI-I-2000-1-005.pdf (143 KBytes)

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},