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

DOI10.1145/3461477MaRDI QIDQ5032035zbMATH OpenOpenAlexFDO

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

Publication date 16 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3461477

zbMATH Keywords

\(k\)-pathparameterized complexityparameterized counting problems

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

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

Cited in

(6)

• Approximately counting approximately-shortest paths in directed acyclic graphs
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
• Determinantal sieving
• Deterministically counting k-paths and trees parameterized by treewidth in single-exponential time

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

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