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

DOI10.1016/j.jda.2010.06.001zbMath1203.90130OpenAlexW2001776351MaRDI QIDQ616992

Henning Fernau, Daniel Binkele-Raible

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

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

Related Items (4)

Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Parameterized measure \& conquer for problems with no small kernels

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• A new algorithm for optimal 2-constraint satisfaction and its implications
• New upper bounds for the problem of maximal satisfiability
• A measure & conquer approach for the analysis of exact algorithms
• New Bounds for MAX-SAT by Clause Learning
• A new approach to proving upper bounds for MAX-2-SAT
• Searching Trees: An Essay
• Exploiting Cycle Structures in Max-SAT
• On the Approximation of Maximum Satisfiability
• New Upper Bounds for Maximum Satisfiability
• Algorithms - ESA 2003
• Graph-Theoretic Concepts in Computer Science

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