Approximate Counting of k-Paths: Deterministic and in Polynomial Space

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

zbMATH Keywords

\(k\)-pathparameterized complexityapproximate counting

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• 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
• Balanced families of perfect hash functions and their applications
• 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