Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
verfasst von : Jesper Nederlof
Erschienen in: Automata, Languages and Programming
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
Given a graph with
n
vertices,
k
terminals and bounded integer weights on the edges, we compute the minimum
Steiner Tree
in
${\mathcal{O}^*}(2^k)$
time and polynomial space, where the
${\mathcal{O}^*}$
notation omits
poly
(
n
,
k
) factors. Among our results are also polynomial-space
$\mathcal{O}^*(2^n)$
algorithms for several
${\mathcal{NP}}$
-complete spanning tree and partition problems.
The previous fastest known algorithms for these problems use the technique of dynamic programming among subsets, and require exponential space. We introduce the concept of branching walks and extend the Inclusion-Exclusion algorithm of Karp for counting Hamiltonian paths. Moreover, we show that our algorithms can also be obtained by applying Möbius inversion on the recurrences used for the dynamic programming algorithms.