New exact algorithms for the 2-constraint satisfaction problem
DOI10.1016/J.TCS.2014.01.010zbMATH Open1290.68144OpenAlexW2041669358MaRDI QIDQ2437759FDOQ2437759
Authors: Alexander Golovnev, Konstantin Kutzkov 
Publication date: 13 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.010
Recommendations
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- Exact Max 2-Sat: Easier and Faster
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Optimal 2-constraint satisfaction via sum-product algorithms
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- A Dynamic Programming Approach to Sequencing Problems
- Applications of a Planar Separator Theorem
- Large induced degenerate subgraphs
- Which problems have strongly exponential complexity?
- Multiplying matrices faster than coppersmith-winograd
- Some optimal inapproximability results
- A new algorithm for optimal 2-constraint satisfaction and its implications
- The complexity of satisfiability of small depth circuits
- Set partitioning via inclusion-exclusion
- Computing Partitions with Applications to the Knapsack Problem
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- A note on the complexity of the chromatic number problem
- A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
- Finding a Maximum Independent Set
- 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
- A new approach to proving upper bounds for MAX-2-SAT
- An exact exponential time algorithm for counting bipartite cliques
- Improved exact algorithms for MAX-SAT
- An exact algorithm for MAX-CUT in sparse graphs
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- New upper bounds for the problem of maximal satisfiability
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
- Balanced coloring of bipartite graphs
- Exact Max 2-Sat: Easier and Faster
Cited In (15)
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
- Local maxima and improved exact algorithm for MAX-2-SAT
- Optimal 2-constraint satisfaction via sum-product algorithms
- A faster polynomial-space algorithm for Max 2-CSP
- A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
- Exact Max 2-Sat: Easier and Faster
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
- A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
- Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
- \(K_4\)-minor-free induced subgraphs of sparse connected graphs
- Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
- Improved exact algorithms for mildly sparse instances of MAX SAT
Uses Software
This page was built for publication: New exact algorithms for the 2-constraint satisfaction problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437759)
