Improving exact algorithms for MAX-2-SAT
From MaRDI portal
Publication:812398
DOI10.1007/s10472-005-7036-zzbMath1086.68058OpenAlexW1984322914MaRDI QIDQ812398
Publication date: 23 January 2006
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10472-005-7036-z
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Redundancy in logic. II: 2CNF and Horn propositional formulae ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ Iterative and core-guided maxsat solving: a survey and assessment ⋮ Improving exact algorithms for MAX-2-SAT
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for the maximum satisfiability problem
- Improving exact algorithms for MAX-2-SAT
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT 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 machine program for theorem-proving
- Theory and Applications of Satisfiability Testing
- Principles and Practice of Constraint Programming – CP 2003
