Improving exact algorithms for MAX-2-SAT

DOI10.1007/S10472-005-7036-ZMaRDI QIDQ812398zbMATH OpenOpenAlexFDO

Authors Haiou Shen, Hantao Zhang

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

zbMATH Keywords

exact algorithmsmaximum satisfiabilitypropositional satisfiability

Mathematics Subject Classification ID

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)

Recommendations

• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Exact algorithms for MAX-SAT
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach

Cites work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A machine program for theorem-proving
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Algorithms for the maximum satisfiability problem
• An Empirical Study of MAX-2-SAT Phase Transitions
• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• scientific article; zbMATH DE number 956857 (Why is no real title available?)
• scientific article; zbMATH DE number 956866 (Why is no real title available?)
• Improving exact algorithms for MAX-2-SAT
• New Upper Bounds for Maximum Satisfiability
• New worst-case upper bounds for SAT
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Solving Max-SAT as weighted CSP
• Theory and Applications of Satisfiability Testing
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(11)

• 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
• Redundancy in logic. II: 2CNF and Horn propositional formulae
• Exact MAX-2SAT solution via lift-and-project closure
• scientific article; zbMATH DE number 1629855 (Why is no real title available?)
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• scientific article; zbMATH DE number 1979498 (Why is no real title available?)
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• Solving MAX-\(r\)-SAT above a tight lower bound
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Improving exact algorithms for MAX-2-SAT

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: Improving exact algorithms for MAX-2-SAT

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