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

DOI10.1007/11814948_26zbMATH Open1187.68258OpenAlexW2158953726MaRDI QIDQ5756576FDOQ5756576

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

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

Mathematics Subject Classification ID

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

Cited In (8)

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

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)