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-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 (12)
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs
- Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
- Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
- Optimal 2-constraint satisfaction via sum-product algorithms
- A faster polynomial-space algorithm for Max 2-CSP
- 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
- A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
- Title not available (Why is that?)
- 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)
