Space saving by dynamic algebraization based on tree-depth
From MaRDI portal
Publication:2411033
DOI10.1007/s00224-017-9751-3zbMath1379.68379OpenAlexW2591652165MaRDI QIDQ2411033
Publication date: 20 October 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-017-9751-3
dynamic programmingtree decompositiontree-depthexponential time algorithmsspace-efficient algorithmszeta transform
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)
Related Items
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for treewidth
- Exact algorithms for exact satisfiability and number of perfect matchings
- On two techniques of combining branching and treewidth
- Treewidth. Computations and approximations
- On treewidth approximations.
- Approximating the number of monomer-dimer coverings of a lattice.
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Tree-depth, subgraph coloring and homomorphism bounds
- Saving space by algebraization
- Planar k-Path in Subexponential Time and Polynomial Space
- Faster Algebraic Algorithms for Path and Packing Problems
- Fourier meets M\"{o}bius: fast subset convolution
- Faster Integer Multiplication
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Limits and Applications of Group Algebras for Parameterized Problems
- Inclusion/Exclusion Meets Measure and Conquer
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Separators for sphere-packings and nearest neighbor graphs
- A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
- A linear time algorithm for finding tree-decompositions of small treewidth
- Parameterized and Exact Computation
- Dimer problem in statistical mechanics-an exact result
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- SOFSEM 2005: Theory and Practice of Computer Science
- [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
