Algorithms for Propositional Model Counting

DOI10.1007/978-3-540-75560-9_35MaRDI QIDQ3498488zbMATHOpenAlexFDO

Authors Marko Samer, Stefan Szeider

Publication date 15 May 2008

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75560-9_35

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Logic in artificial intelligence (68T27)

Recommendations

• Algorithms for propositional model counting
• Two approximate algorithms for model counting
• Counting propositional models
• Solving #SAT and MAXSAT by Dynamic Programming
• Counting models for 2SAT and 3SAT formulae

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximating clique-width and branch-width
• Conjunctive-query containment and constraint satisfaction
• Constraint Satisfaction with Bounded Treewidth Revisited
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Fast multiplication of large numbers
• Faster integer multiplication
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Graph minors. X: Obstructions to tree-decomposition
• Hypertree decompositions and tractable queries
• Linear time solvable optimization problems on graphs of bounded clique-width
• Memory requirements for table computations in partial \(k\)-tree algorithms
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• On the hardness of approximate reasoning
• Parametrized complexity theory.
• SOFSEM 2005: Theory and Practice of Computer Science
• Solving #SAT Using Vertex Covers
• The complexity of computing the permanent
• Treewidth. Computations and approximations
• Treewidth: computational experiments

Cited in

(21)

• Solving \#SAT using extension rules
• On preprocessing techniques and their impact on propositional model counting
• Counting models for 2SAT and 3SAT formulae
• Counting propositional models
• Leveraging belief propagation, backtrack search, and statistics for model counting
• On enumerating short projected models
• Constraint satisfaction with bounded treewidth revisited
• Reconstructive algorithm based on extension rule for solving \#SAT incrementally
• Hypergraph acyclicity and propositional model counting
• A bottom-up algorithm for solving \#2SAT
• Solving \#SAT using vertex covers
• Complexity and Algorithms for Well-Structured k-SAT Instances
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
• An exhaustive DPLL algorithm for model counting
• Solving projected model counting by utilizing treewidth and its limits
• On the expressive power of CNF formulas of bounded tree- and clique-width
• Counting solutions to CSP using generating polynomials
• Volume Computation for Boolean Combination of Linear Arithmetic Constraints
• Algorithms for propositional model counting
• Two approximate algorithms for model counting
• \#SAT solving algorithms based on extension rule using heuristic strategies

This page was built for publication: Algorithms for Propositional Model Counting

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