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

DOI10.1007/978-3-540-85238-4_45MaRDI QIDQ3599157zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A new upper bound for Max-2-SAT: A graph-theoretic approach
• New Upper Bounds for Maximum Satisfiability
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• scientific article; zbMATH DE number 1500507
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cites work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• A new approach to proving upper bounds for MAX-2-SAT
• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1629855 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• 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
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(10)

• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• A tighter upper bound for random MAX \(2\)-SAT
• New upper bounds for the problem of maximal satisfiability
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• New Upper Bounds for Maximum Satisfiability
• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• 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
• Improving exact algorithms 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 Q3599157)