Counting Paths and Packings in Halves

DOI10.1007/978-3-642-04128-0_52MaRDI QIDQ3639276zbMATH OpenOpenAlexFDO

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

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

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) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Narrow sieves for parameterized paths and packings
• Partitioning into sets of bounded cardinality
• Packing paths perfectly

Cited in

(21)

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

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

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