Approximate Counting of k-Paths: Deterministic and in Polynomial Space
From MaRDI portal
Publication:5091173
DOI10.4230/LIPIcs.ICALP.2019.24OpenAlexW2965200911MaRDI QIDQ5091173
Meirav Zehavi, Saket Saurabh, Andreas Björklund, Daniel Lokshtanov
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10600/pdf/LIPIcs-ICALP-2019-24.pdf
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Representative families: a unified tradeoff-based approach
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
- Narrow sieves for parameterized paths and packings
- Finding, Minimizing, and Counting Weighted Subgraphs
- Saving space by algebraization
- Extremal Combinatorics
- Planar k-Path in Subexponential Time and Polynomial Space
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
- Mixing Color Coding-Related Techniques
- Faster Algebraic Algorithms for Path and Packing Problems
- Counting Paths and Packings in Halves
- Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
- Balanced Hashing, Color Coding and Approximate Counting
- Color-coding
- Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
- Kernelization
- The Parameterized Complexity of Counting Problems
- LIMITS and Applications of Group Algebras for Parameterized Problems
- Homomorphisms are a good basis for counting small subgraphs
- Extensor-coding
- A time- and space-optimal algorithm for the many-visits TSP
- Spotting Trees with Few Leaves
- Determinant Sums for Undirected Hamiltonicity
- Probability and Computing
- Parameterized Algorithms
- Research in Computational Molecular Biology
This page was built for publication: Approximate Counting of k-Paths: Deterministic and in Polynomial Space
