Algorithms for Propositional Model Counting

DOI10.1007/978-3-540-75560-9_35zbMath1137.68623OpenAlexW2069680070MaRDI QIDQ3498488

Stefan Szeider, Marko Samer

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)

Related Items (8)

Constraint satisfaction with bounded treewidth revisited ⋮ On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width ⋮ On the expressive power of CNF formulas of bounded tree- and clique-width ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ Counting solutions to CSP using generating polynomials ⋮ Solving \#SAT using vertex covers ⋮ Algorithms for propositional model counting ⋮ Volume Computation for Boolean Combination of Linear Arithmetic Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Hypertree decompositions and tractable queries
• Graph minors. X: Obstructions to tree-decomposition
• Treewidth. Computations and approximations
• Memory requirements for table computations in partial \(k\)-tree algorithms
• Conjunctive-query containment and constraint satisfaction
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Linear time solvable optimization problems on graphs of bounded clique-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Fast multiplication of large numbers
• On the hardness of approximate reasoning
• Constraint Satisfaction with Bounded Treewidth Revisited
• Constraint solving via fractional edge covers
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• SOFSEM 2005: Theory and Practice of Computer Science
• Solving #SAT Using Vertex Covers
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

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