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

DOI10.1145/3461477OpenAlexW3183157744MaRDI QIDQ5032035FDOQ5032035

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

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

zbMATH Keywords

\(k\)-pathparameterized complexityparameterized counting problems

Mathematics Subject Classification ID

Computer science (68-XX)

Cited In (3)

• 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

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)