A new upper bound for Max-2-SAT: A graph-theoretic approach

DOI10.1016/J.JDA.2010.06.001zbMATH Open1203.90130OpenAlexW2001776351MaRDI QIDQ616992FDOQ616992

Authors Daniel Binkele-Raible, Henning Fernau 

Publication date 20 January 2011

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2010.06.001

zbMATH Keywords

measure and conquermaximum 2-satisfiability problemmoderately exponential-time algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Publication:4938646
• New Upper Bounds for Maximum Satisfiability
• scientific article; zbMATH DE number 1500507
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• New upper bounds for the problem of maximal satisfiability
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• A tighter upper bound for random MAX \(2\)-SAT
• scientific article; zbMATH DE number 1522934

Cites work

• scientific article; zbMATH DE number 1629855 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A measure \& conquer approach for the analysis of exact algorithms
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A new approach to proving upper bounds for MAX-2-SAT
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Exploiting Cycle Structures in Max-SAT
• Graph-Theoretic Concepts in Computer Science
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New Bounds for MAX-SAT by Clause Learning
• New Upper Bounds for Maximum Satisfiability
• New inference rules for Max-SAT
• New upper bounds for the problem of maximal satisfiability
• On the Approximation of Maximum Satisfiability
• Searching Trees: An Essay
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(10)

• Improved exact algorithms for mildly sparse instances of MAX SAT
• Parameterized measure \& conquer for problems with no small kernels
• New upper bounds for the problem of maximal satisfiability
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• scientific article; zbMATH DE number 1405665 (Why is no real title available?)
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• New Upper Bounds for Maximum Satisfiability
• New exact algorithms for the 2-constraint satisfaction problem
• Local maxima and improved exact algorithm for MAX-2-SAT

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: A new upper bound for Max-2-SAT: A graph-theoretic approach

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