Exact Algorithms for MAX-SAT
From MaRDI portal
Publication:4916231
DOI10.1016/S1571-0661(04)80663-7zbMath1261.68073OpenAlexW1993837454MaRDI QIDQ4916231
Haiou Shen, Felip Manyà, Han-Tao Zhang
Publication date: 19 April 2013
Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s1571-0661(04)80663-7
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
An efficient solver for weighted Max-SAT ⋮ MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability ⋮ On preprocessing for weighted MaxSAT ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ Resolution for Max-SAT ⋮ An Empirical Study of MAX-2-SAT Phase Transitions
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for the maximum satisfiability problem
- A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
- Solving propositional satisfiability problems
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- New worst-case upper bounds for SAT
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- An Empirical Study of MAX-2-SAT Phase Transitions
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- New Upper Bounds for Maximum Satisfiability
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Theory and Applications of Satisfiability Testing
- Faster exact algorithms for hard problems: A parameterized point of view
This page was built for publication: Exact Algorithms for MAX-SAT