Solving \#SAT using vertex covers

DOI10.1007/S00236-007-0056-XMaRDI QIDQ2464035zbMATH OpenOpenAlexFDO

Authors N. Nishimura, Prabhakar Ragde, Stefan Szeider

Publication date 10 December 2007

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-007-0056-x

zbMATH Keywords

obstruction graph

Mathematics Subject Classification ID

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

Recommendations

• Solving #SAT Using Vertex Covers
• Model counting for formulas of bounded clique-width
• New width parameters for model counting
• Counting truth assignments of formulas of bounded tree-width or clique-width
• New width parameters for SAT and \#SAT

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Algorithms for Propositional Model Counting
• Approximating clique-width and branch-width
• Backdoor sets for DLL subsolvers
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Graph-modeled data clustering: Exact algorithms for clique generation
• Improved Parameterized Upper Bounds for Vertex Cover
• On the clique-width of some perfect graph classes
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Satisfiable formulas closed under replacement
• The Parameterized Complexity of Counting Problems
• The complexity of computing the permanent
• Theory and Applications of Satisfiability Testing
• Upper bounds to the clique width of graphs
• Vertex cover: Further observations and further improvements

Cited in

(15)

• Computation of Renameable Horn Backdoors
• Satisfiability of acyclic and almost acyclic CNF formulas
• New width parameters for SAT and \#SAT
• Are hitting formulas hard for resolution?
• Backdoors to satisfaction
• Backdoor sets of quantified Boolean formulas
• Tensor network contractions for \#SAT
• Algorithms for propositional model counting
• Solving #SAT Using Vertex Covers
• Strong backdoors to nested satisfiability
• Model counting for formulas of bounded clique-width
• Better algorithms for satisfiability problems for formulas of bounded rank-width
• Community structure inspired algorithms for SAT and \#SAT
• Backdoors to tractable answer set programming
• Backdoors into two occurrences

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 Q2464035)