Solving \#SAT using vertex covers

DOI10.1007/S00236-007-0056-XzbMATH Open1133.68073OpenAlexW2093939144MaRDI QIDQ2464035FDOQ2464035

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

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

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)

Cites Work

• The complexity of computing the permanent
• A partial k-arboretum of graphs with bounded treewidth
• 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
• On the clique-width of some perfect graph classes
• Title not available (Why is that?)
• 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
• Vertex cover: Further observations and further improvements
• The Parameterized Complexity of Counting Problems
• Graph-modeled data clustering: Exact algorithms for clique generation
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Backdoor sets for DLL subsolvers
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Algorithms for Propositional Model Counting
• Satisfiable formulas closed under replacement

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)