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

DOI10.4230/LIPICS.ICALP.2019.24MaRDI QIDQ5091173zbMATH OpenOpenAlexFDO

Authors Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

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\)-pathapproximate countingparameterized complexity

Mathematics Subject Classification ID

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

Recommendations

• Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space
• scientific article; zbMATH DE number 1979521
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Extensor-coding
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs

Cites work

• A time- and space-optimal algorithm for the many-visits TSP
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Balanced families of perfect hash functions and their applications
• Balanced hashing, color coding and approximate counting
• Color-coding
• Counting Paths and Packings in Halves
• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• Determinant sums for undirected Hamiltonicity
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Extensor-coding
• Extremal combinatorics. With applications in computer science
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Finding, minimizing, and counting weighted subgraphs
• Homomorphisms are a good basis for counting small subgraphs
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• Kernelization. Theory of parameterized preprocessing
• LIMITS and applications of group algebras for parameterized problems
• Mixing Color Coding-Related Techniques
• Narrow sieves for parameterized paths and packings
• Parameterized algorithms
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Planar k-path in subexponential time and polynomial space
• Probability and Computing
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• Representative families: a unified tradeoff-based approach
• Research in Computational Molecular Biology
• Saving space by algebraization
• Spotting trees with few leaves
• The Parameterized Complexity of Counting Problems

Cited in

(1)

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

This page was built for publication: Approximate Counting of k-Paths: Deterministic and in Polynomial Space

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