User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse





On Steiner trees and minimum spanning trees in hypergraphs


Polzin,  Tobias
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

(Any fulltext), 11KB

Supplementary Material (public)
There is no public supplementary material available

Polzin, T., & Vahdati, S.(2001). On Steiner trees and minimum spanning trees in hypergraphs (MPI-I-2001-1-005). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-6D1F-E
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.