×

zbMATH — the first resource for mathematics

Dynamic programming on tree decompositions using generalised fast subset convolution. (English) Zbl 1256.68157
Fiat, Amos (ed.) et al., Algorithms – ESA 2009. 17th annual European symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04127-3/pbk). Lecture Notes in Computer Science 5757, 566-577 (2009).
Summary: In this paper, we show that algorithms on tree decompositions can be made faster with the use of generalisations of fast subset convolution. Amongst others, this gives algorithms that, for a graph, given with a tree decomposition of width \(k\), solve the dominated set problem in \(O(n k ^{2} 3^{k })\) time and the problem to count the number of perfect matchings in \(O ^{ \ast }(2^{k })\) time. Using a generalisation of fast subset convolution, we obtain faster algorithms for all \([\rho ,\sigma ]\)-domination problems with finite or cofinite \(\rho \) and \(\sigma \) on tree decompositions. These include many well-known graph problems. We give additional results on many more graph covering and partitioning problems.
For the entire collection see [Zbl 1173.68009].

MSC:
68W05 Nonnumerical algorithms
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI