Faster exact solutions for Max2Sat

DOI10.1007/3-540-46521-9_15MaRDI QIDQ2728900zbMATH OpenFDO

Authors Jens Gramm, Rolf Niedermeier

Publication date 4 November 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46521-9_15

zbMATH Keywords

exact algorithmsMax2SatMaximum CutNP-complete problemsparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computing methodologies and applications (68U99)

Recommendations

• Improved exact algorithms for MAX-SAT
• scientific article; zbMATH DE number 2086240
• Improving exact algorithms for MAX-2-SAT
• Exact algorithms for MAX-SAT
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• Theory and Applications of Satisfiability Testing
• Exact Max-SAT solvers for over-constrained problems
• scientific article; zbMATH DE number 1552232
• Improved approximation algorithms for MAX SAT

Cited in

(13)

• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Worst-case study of local search for MAX-\(k\)-SAT.
• Improved exact algorithms for MAX-SAT
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Exact MAX-2SAT solution via lift-and-project closure
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• A Spectral Method for MAX2SAT in the Planted Solution Model
• Exact Max 2-Sat: Easier and Faster
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Solving sparse instances of Max SAT via width reduction and greedy restriction

This page was built for publication: Faster exact solutions for Max2Sat

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