Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
A Faster Algorithm for the Steiner Tree Problem
verfasst von : Daniel Mölle, Stefan Richter, Peter Rossmanith
Erschienen in: STACS 2006
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
For decades, the algorithm providing the smallest proven worst-case running time (with respect to the number of terminals) for the Steiner tree problem has been the one by Dreyfus and Wagner. In this paper, a new algorithm is developed, which improves the running time from
O
(3
k
n
+2
k
n
2
+
n
3
) to (2+
δ
)
k
·
poly
(
n
) for arbitrary but fixed
δ
> 0. Like its predecessor, this algorithm follows the dynamic programming paradigm. Whereas in effect the Dreyfus–Wagner recursion splits the optimal Steiner tree in two parts of arbitrary sizes, our approach looks for a set of nodes that separate the tree into parts containing only few terminals. It is then possible to solve an instance of the Steiner tree problem more efficiently by combining partial solutions.