Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

DOI10.1007/11786986_48zbMath1170.68651OpenAlexW2112109045MaRDI QIDQ3613789

Andreas Björklund, Thore Husfeldt

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_48

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

Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG, Computing optimal Steiner trees in polynomial space, Exact algorithms for \(L(2,1)\)-labeling of graphs, Branch and recharge: exact algorithms for generalized domination, Solving connected dominating set faster than \(2^n\), On the minimum feedback vertex set problem: Exact and enumeration algorithms, Exponential-time approximation of weighted set cover