Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Approaches to the Steiner Problem in Networks
verfasst von : Tobias Polzin, Siavash Vahdati-Daneshmand
Erschienen in: Algorithmics of Large and Complex Networks
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The Steiner problem in networks is the problem of connecting a set of required vertices in a weighted graph at minimum cost. This is a classical
${\mathcal {NP}}$
-hard problem and a fundamental problem in network design with many practical applications.
We approach this problem by various means: Relaxations, which relax the feasibility constraints, to get close to an optimal solution; heuristics to find good, but not necessarily optimal solutions; and reductions to simplify problem instances without abandoning the optimal solution. We have integrated these components into an exact algorithm that has achieved outstanding results in practice.
In this article, we first provide a brief overview on the main algorithmic developments related to our work on this problem, citing our and others’ (already published) works. Then we focus on some central concepts, presenting detailed results on selected topics that offer special insight and potential for further improvement.