MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
From MaRDI portal
Publication:5756576
DOI10.1007/11814948_26zbMath1187.68258OpenAlexW2158953726MaRDI QIDQ5756576
Alexander Wolpert, Evgeny Dantsin
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
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (8)
New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ 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 ⋮ A new upper bound for \(( n , 3)\)-MAX-SAT ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps
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
