2010 | OriginalPaper | Buchkapitel
Faster Algorithms on Branch and Clique Decompositions
verfasst von : Hans L. Bodlaender, Erik Jan van Leeuwen, Johan M. M. van Rooij, Martin Vatshelle
Erschienen in: Mathematical Foundations of Computer Science 2010
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
We combine two techniques recently introduced to obtain faster dynamic programming algorithms for optimization problems on graph decompositions. The unification of generalized fast subset convolution and fast matrix multiplication yields significant improvements to the running time of previous algorithms for several optimization problems. As an example, we give an
$O^{*}(3^{\frac{\omega}{2}k})$
time algorithm for Minimum Dominating Set on graphs of branchwidth
k
, improving on the previous
O
*
(4
k
) algorithm. Here
ω
is the exponent in the running time of the best matrix multiplication algorithm (currently
ω
< 2.376). For graphs of cliquewidth
k
, we improve from
O
*
(8
k
) to
O
*
(4
k
). We also obtain an algorithm for counting the number of perfect matchings of a graph, given a branch decomposition of width
k
, that runs in time
$O^{*}(2^{\frac{\omega}{2}k})$
. Generalizing these approaches, we obtain faster algorithms for all so-called [
ρ
,
σ
]-domination problems on branch decompositions if
ρ
and
σ
are finite or cofinite. The algorithms presented in this paper either attain or are very close to natural lower bounds for these problems.