A bottom-up algorithm for solving \#2SAT

DOI10.1093/JIGPAL/JZAA009zbMATH Open1497.68357OpenAlexW3022611987MaRDI QIDQ3386918FDOQ3386918

Authors: Guillermo De Ita, J. Raymundo Marcial-Romero, J. A. Hernández-Servín 

Publication date: 8 January 2021

Published in: Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/jigpal/jzaa009

Recommendations

• An enumerative algorithm for \#2SAT
• A threshold for a polynomial solution of \#2SAT
• Counting models for 2SAT and 3SAT formulae
• Algorithms for Propositional Model Counting
• Algorithms for propositional model counting

zbMATH Keywords

graph decompositioncounting modelsenumerative algorithm\#2SAT

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Computational aspects of satisfiability (68R07)

Cited In (4)

• An enumerative algorithm for \#2SAT
• Almost 2-SAT is fixed-parameter tractable
• Reconstructive algorithm based on extension rule for solving \#SAT incrementally
• On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions

This page was built for publication: A bottom-up algorithm for solving \#2SAT

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