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

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

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)

Cites Work

• A measure & conquer approach for the analysis of exact algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Title not available (Why is that?)
• New inference rules for Max-SAT
• Exploiting Cycle Structures in Max-SAT
• Searching Trees: An Essay
• On the Approximation of Maximum Satisfiability
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• 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
• Title not available (Why is that?)
• 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
• Graph-Theoretic Concepts in Computer Science
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• New upper bounds for the problem of maximal satisfiability
• An approximation algorithm for MAX-2-SAT with cardinality constraint

Cited In (10)

• New upper bounds for the problem of maximal satisfiability
• New exact algorithms for the 2-constraint satisfaction problem
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
• Title not available (Why is that?)
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• Parameterized measure \& conquer for problems with no small kernels
• Improved exact algorithms for mildly sparse instances of MAX SAT
• New Upper Bounds for Maximum Satisfiability

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)