An enumerative algorithm for \#2SAT

DOI10.1016/J.ENDM.2014.08.012MaRDI QIDQ283678zbMATH OpenOpenAlexFDO

Authors Guillermo de Ita Luna, J. Raymundo Marcial-Romero, Yolanda Moyao

Publication date 13 May 2016

Full work available at URL https://doi.org/10.1016/j.endm.2014.08.012

zbMATH Keywords

\#SAT problemcounting modelsefficient countingenumerative algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05)

Recommendations

• Exact enumeration of satisfiable 2-SAT formulae
• A bottom-up algorithm for solving \#2SAT
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• On the relations between SAT and CSP enumerative algorithms
• scientific article; zbMATH DE number 1500507
• On the number of 2-SAT functions
• The Multi-SAT algorithm
• scientific article; zbMATH DE number 1342213
• Algorithms for Sat and upper bounds on their complexity
• The number of 2-SAT functions

Cites work

• scientific article; zbMATH DE number 1566488 (Why is no real title available?)
• Counting models for 2SAT and 3SAT formulae
• Improved algorithms for counting solutions in constraint satisfaction problems
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• On the hardness of approximate reasoning
• Theory and Applications of Satisfiability Testing

Cited in

(2)

• Reconstructive algorithm based on extension rule for solving \#SAT incrementally
• A bottom-up algorithm for solving \#2SAT

This page was built for publication: An enumerative algorithm for \#2SAT

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