Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time

DOI10.1145/3125500zbMath1452.68133arXiv1306.4111OpenAlexW2963965405MaRDI QIDQ4554938

Łukasz Kowalik, Petteri Kaski, Andreas Björklund, Andreas Bjöurklund

Publication date: 12 November 2018

Published in: ACM Transactions on Algorithms, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.4111

zbMATH Keywords

matrix multiplicationFPT algorithmscounting matchingscounting pathsmeet in the middlecounting low pathwidth graphscounting packings

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Counting Subgraphs in Degenerate Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Assigning channels via the meet-in-the-middle approach ⋮ Unnamed Item ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space