Exact algorithms for exact satisfiability and number of perfect matchings

DOI10.1007/s00453-007-9149-8zbMath1170.68046OpenAlexW1988642505MaRDI QIDQ958212

Thore Husfeldt, Andreas Björklund

Publication date: 2 December 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9149-8

zbMATH Keywords

set coverexact algorithmsset partitionexact satisfabilitynumber of perfect matchings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (20)

Partition into triangles on bounded degree graphs ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Exponential approximation schemata for some network design problems ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration ⋮ Trimmed Moebius inversion and graphs of bounded degree ⋮ When polynomial approximation meets exact computation ⋮ Improved algorithms for the general exact satisfiability problem ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Invitation to Algorithmic Uses of Inclusion–Exclusion ⋮ When polynomial approximation meets exact computation ⋮ Solving the train marshalling problem by inclusion-exclusion ⋮ Inclusion/exclusion meets measure and conquer ⋮ APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME ⋮ Faster graph coloring in polynomial space ⋮ Partitioning into Sets of Bounded Cardinality ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Unnamed Item ⋮ Exponential-time quantum algorithms for graph coloring problems ⋮ Faster exponential-time algorithms in graphs of bounded average degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for four variants of the exact satisfiability problem
• The complexity of computing the permanent
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• Enumerating maximal independent sets with applications to graph colouring.
• Matrix multiplication via arithmetic progressions
• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• Pathwidth of cubic graphs and exact algorithms
• Matching theory
• Dynamic programming meets the principle of inclusion and exclusion
• A note on the complexity of the chromatic number problem
• Heuristics for semirandom graph problems
• New algorithms for exact satisfiability
• A new algorithm for optimal 2-constraint satisfaction and its implications
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Expected Computation Time for Hamiltonian Path problem
• A New Algorithm for Generating All the Maximal Independent Sets
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Worst-case time bounds for coloring and satisfiability problems
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• Parameterized and Exact Computation
• An algorithm for the chromatic number of a graph
• A machine program for theorem-proving
• SOFSEM 2005: Theory and Practice of Computer Science
• Automata, Languages and Programming
• Graph-Theoretic Concepts in Computer Science
• Recent Advances in Constraints
• On cliques in graphs

This page was built for publication: Exact algorithms for exact satisfiability and number of perfect matchings