A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach

DOI10.1007/978-3-540-85238-4_45zbMath1173.68539OpenAlexW1841339196MaRDI QIDQ3599157

Daniel Raible, Henning Fernau

Publication date: 3 February 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_45

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• 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 Bounds for MAX-SAT by Clause Learning
• A new approach to proving upper bounds for MAX-2-SAT
• 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