Saving space by algebraization
From MaRDI portal
Publication:2875160
DOI10.1145/1806689.1806735zbMath1293.68148OpenAlexW2048068744MaRDI QIDQ2875160
Daniel Lokshtanov, Jesper Nederlof
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806735
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (23)
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ A faster FPTAS for the unbounded knapsack problem ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Exponential approximation schemata for some network design problems ⋮ Algebraic algorithms for variants of subset sum ⋮ A Pseudo-Polynomial Time Algorithm for Solving the Knapsack Problem in Polynomial Space ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ A gentle introduction to applications of algorithmic metatheorems for space and circuit classes ⋮ Efficient dissection of bicomposite problems with cryptanalytic applications ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Packing resizable items with application to video delivery over wireless networks ⋮ Faster Pseudopolynomial Time Algorithms for Subset Sum ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ Unnamed Item ⋮ Hardness of approximation for knapsack problems
This page was built for publication: Saving space by algebraization
