Leveraging belief propagation, backtrack search, and statistics for model counting

DOI10.1007/s10479-009-0680-7zbMath1225.90108OpenAlexW2066514569MaRDI QIDQ545553

Lukas Kroc, Bart Selman, Ashish Sabharwal

Publication date: 22 June 2011

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1370

zbMATH Keywords

upper boundsnumber of solutionslower boundsBoolean satisfiabilitySATmodel countingbpcountminicount

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Approximate Model Counting via Extension Rule ⋮ Two approximate algorithms for model counting

Uses Software

• MiniSat
• Walksat
• DIMACS
• RSat

Cites Work

• The complexity of computing the permanent
• CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation
• A new look at survey propagation and its generalizations
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Characterizing Propagation Methods for Boolean Satisfiability
• Stochastic Boolean satisfiability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item