A new approach to proving upper bounds for MAX-2-SAT

DOI10.1145/1109557.1109559zbMath1192.68368OpenAlexW4256152130WikidataQ56288412 ScholiaQ56288412MaRDI QIDQ3581524

Arist Kojevnikov, Alexander S. Kulikov

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109559

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ A new upper bound for Max-2-SAT: A graph-theoretic approach ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Fast algorithms for max independent set ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ 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 ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3 ⋮ Pathwidth of cubic graphs and exact algorithms

Uses Software

• MAX-2-SAT

This page was built for publication: A new approach to proving upper bounds for MAX-2-SAT