Solving #SAT and MAXSAT by Dynamic Programming

DOI10.1613/JAIR.4831MaRDI QIDQ3196312zbMATH OpenOpenAlexFDO

Authors Sigve Hortemo Sæther, Jan Arne Telle, Martin Vatshelle

Publication date 29 October 2015

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/jair.4831

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Dynamic programming (90C39)

Recommendations

• Solving MaxSAT and \#SAT on structured CNF formulas
• On Solving the Partial MAX-SAT Problem
• A logical approach to efficient Max-SAT solving
• SAT-based MaxSAT algorithms
• scientific article; zbMATH DE number 6297727
• Solving MAX-\(r\)-SAT above a tight lower bound
• Analysis and solving SAT and MAX-SAT problems using an L-partition approach
• Solving Max-SAT as weighted CSP
• Exact algorithms for MAX-SAT

Cited in

(14)

• Tractability beyond -acyclicity for conjunctive queries with negation and SAT
• Exploiting Database Management Systems and Treewidth for Counting
• New width parameters for SAT and \#SAT
• Solving projected model counting by utilizing treewidth and its limits
• Reducing treewidth for SAT-related problems using simple liftings
• Solving MaxSAT and \#SAT on structured CNF formulas
• On efficiently solvable cases of quantum \(k\)-SAT
• On efficiently solvable cases of quantum k-SAT
• Treewidth with a quantifier alternation revisited
• scientific article; zbMATH DE number 7378698 (Why is no real title available?)
• Algorithms for Propositional Model Counting
• \#SAT solving algorithms based on extension rule using heuristic strategies
• Lower bounds on the mim-width of some graph classes
• Sum-of-Products with Default Values: Algorithms and Complexity Results

This page was built for publication: Solving #SAT and MAXSAT by Dynamic Programming

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