Solving #SAT Using Vertex Covers

DOI10.1007/11814948_36MaRDI QIDQ5756553zbMATH OpenOpenAlexFDO

Authors N. Nishimura, Stefan Szeider, Prabhakar Ragde

Publication date 4 September 2007

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

Full work available at URL https://doi.org/10.1007/11814948_36

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Solving \#SAT using vertex covers
• New width parameters for model counting
• Model counting for formulas of bounded clique-width
• New width parameters for SAT and \#SAT
• Counting truth assignments of formulas of bounded tree-width or clique-width

Cited in

(8)

• Solving \#SAT using vertex covers
• Learning to assign degrees of belief in relational domains
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• Model counting for formulas of bounded clique-width
• Better algorithms for satisfiability problems for formulas of bounded rank-width
• Algorithms for Propositional Model Counting
• Complexity and Algorithms for Well-Structured k-SAT Instances
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors

This page was built for publication: Solving #SAT Using Vertex Covers

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