Partitioning into Sets of Bounded Cardinality

DOI10.1007/978-3-642-11269-0_21zbMath1273.68271OpenAlexW1497895992MaRDI QIDQ3656867

Mikko Koivisto

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items

Partition into triangles on bounded degree graphs ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ De Sitter and power-law solutions in non-local Gauss–Bonnet gravity ⋮ Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ Unnamed Item ⋮ Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching ⋮ Partition into Triangles on Bounded Degree Graphs ⋮ Unnamed Item ⋮ Faster exponential-time algorithms in graphs of bounded average degree

Cites Work

• The complexity of computing the permanent
• Matrix multiplication via arithmetic progressions
• Exact algorithms for exact satisfiability and number of perfect matchings
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Fourier meets M\"{o}bius: fast subset convolution
• Set Partitioning via Inclusion-Exclusion
• Probability Inequalities for Sums of Bounded Random Variables