Solving \#SAT using vertex covers

DOI10.1007/s00236-007-0056-xzbMath1133.68073OpenAlexW2093939144MaRDI QIDQ2464035

Stefan Szeider, Prabhakar Ragde, Naomi Nishimura

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

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

Related Items (11)

Community Structure Inspired Algorithms for SAT and #SAT ⋮ Backdoors to Satisfaction ⋮ Satisfiability of acyclic and almost acyclic CNF formulas ⋮ Tensor network contractions for \#SAT ⋮ Computation of Renameable Horn Backdoors ⋮ Are hitting formulas hard for resolution? ⋮ New width parameters for SAT and \#SAT ⋮ Algorithms for propositional model counting ⋮ Backdoor sets of quantified Boolean formulas ⋮ Backdoors to tractable answer set programming ⋮ Backdoors into Two Occurrences

Cites Work

• The complexity of computing the permanent
• Graph-modeled data clustering: Exact algorithms for clique generation
• Backdoor sets for DLL subsolvers
• A partial k-arboretum of graphs with bounded treewidth
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Upper bounds to the clique width of graphs
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Approximating clique-width and branch-width
• Vertex Cover: Further Observations and Further Improvements
• Algorithms for Propositional Model Counting
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• The Parameterized Complexity of Counting Problems
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Theory and Applications of Satisfiability Testing
• Improved Parameterized Upper Bounds for Vertex Cover
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Unnamed Item
• Unnamed Item

This page was built for publication: Solving \#SAT using vertex covers