Advertisement
Published in:
2009 | OriginalPaper | Chapter
Approaches to the Steiner Problem in Networks
Authors : Tobias Polzin, Siavash Vahdati-Daneshmand
Published in: Algorithmics of Large and Complex Networks
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.