A new algorithm for MAX-2-SAT

DOI10.1007/3-540-46541-3_5MaRDI QIDQ4501522zbMATH OpenFDO

Authors Edward A. Hirsch

Publication date 6 May 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-46541-3_5

zbMATH Keywords

satisfiability problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• New Upper Bounds for Maximum Satisfiability
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• A new upper bound for Max-2-SAT: A graph-theoretic approach

Cited in

(24)

• Almost 2-SAT is fixed-parameter tractable
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Worst-case study of local search for MAX-\(k\)-SAT.
• MAX-2-SAT
• On the lower bounds of random Max 3 and 4-SAT
• A tighter upper bound for random MAX \(2\)-SAT
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New exact algorithms for the 2-constraint satisfaction problem
• An enumerative algorithm for \#2SAT
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• An Empirical Study of MAX-2-SAT Phase Transitions
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• 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
• On the Lower Bounds of Random Max 3 and 4-SAT
• Exact algorithms for MAX-SAT
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• A Spectral Method for MAX2SAT in the Planted Solution Model
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Improving exact algorithms for MAX-2-SAT
• An upper (lower) bound for Max (Min) CSP
• Solving sparse instances of Max SAT via width reduction and greedy restriction

This page was built for publication: A new algorithm for MAX-2-SAT

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