Space saving by dynamic algebraization

DOI10.1007/978-3-319-06686-8_29MaRDI QIDQ4981176zbMATH OpenOpenAlexFDO

Authors Huiwen Yu, Martin Fürer

Publication date 24 June 2014

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.3414

zbMATH Keywords

dynamic programmingtree decompositionexponential-time algorithmsspace-efficient algorithmzeta transform

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithm based on tree decompositions in polynomial space. We show how to construct a tree decomposition and extend the algebraic techniques of Lokshtanov and Nederlof such that the dynamic programming algorithm runs in time $O^{\ast }(2^h)$, where $h$ is the maximum number of vertices in the union of bags on the root to leaf paths on a given tree decomposition, which is a parameter closely related to the tree-depth of a graph. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.

Recommendations

• Space saving by dynamic algebraization based on tree-depth
• scientific article; zbMATH DE number 2149351
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Tree decompositions of graphs: saving memory in dynamic programming

Cited in

(9)

• Computing treedepth in polynomial space and linear FPT time
• Width, depth, and space: tradeoffs between branching and dynamic programming
• Algebras for tree decomposable graphs
• On space efficiency of algorithms working on structural decompositions of graphs
• On space efficiency of algorithms working on structural decompositions of graphs
• scientific article; zbMATH DE number 2149351 (Why is no real title available?)
• Space saving by dynamic algebraization based on tree-depth
• Homomorphic hashing for sparse coefficient extraction
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution

This page was built for publication: Space saving by dynamic algebraization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4981176)