A new approach to proving upper bounds for MAX-2-SAT
From MaRDI portal
Publication:3581524
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
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
This page was built for publication: A new approach to proving upper bounds for MAX-2-SAT
