MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in \mathcal{O}(2ⁿ) Time

DOI10.1007/11814948_26MaRDI QIDQ5756576zbMATHOpenAlexFDO

Authors E. Ya. Dantsin, Alexander Wolpert

Publication date 4 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11814948_26

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• New Bounds for MAX-SAT by Clause Learning
• Exact algorithms for MAX-SAT
• scientific article; zbMATH DE number 1522934
• Publication:4938646
• Improved exact algorithms for mildly sparse instances of MAX SAT

Cited in

(8)

• Improved exact algorithms for mildly sparse instances of MAX SAT
• New upper bounds for the problem of maximal satisfiability
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
• A new upper bound for \(( n , 3)\)-MAX-SAT
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• New exact algorithms for the 2-constraint satisfaction problem

This page was built for publication: MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time

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