A bottom-up algorithm for solving \#2SAT

DOI10.1093/JIGPAL/JZAA009MaRDI QIDQ3386918zbMATH OpenOpenAlexFDO

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

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)

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

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)