Counting Paths and Packings in Halves

DOI10.1007/978-3-642-04128-0_52zbMath1256.05230OpenAlexW1808823193MaRDI QIDQ3639276

Thore Husfeldt, Mikko Koivisto, Andreas Björklund, Petteri Kaski

Publication date: 29 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04128-0_52

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Counting Subgraphs in Degenerate Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ Assigning channels via the meet-in-the-middle approach ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Number of cycles of small length in a graph ⋮ Evaluation of permanents in rings and semirings ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Computing generalized convolutions faster than brute force ⋮ Faster algorithms for finding and counting subgraphs ⋮ Fast monotone summation over disjoint sets ⋮ On Counting Parameterized Matching and Packing ⋮ Inclusion/exclusion meets measure and conquer ⋮ Enumerating simple paths from connected induced subgraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Balanced Hashing, Color Coding and Approximate Counting

This page was built for publication: Counting Paths and Packings in Halves