New exact algorithms for the 2-constraint satisfaction problem
From MaRDI portal
Publication:2437759
DOI10.1016/j.tcs.2014.01.010zbMath1290.68144OpenAlexW2041669358MaRDI QIDQ2437759
Konstantin Kutzkov, Alexander Golovnev
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
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
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 ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Unnamed Item ⋮ $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs
Uses Software
Cites Work
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- An exact exponential time algorithm for counting bipartite cliques
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- Large induced degenerate subgraphs
- A note on the complexity of the chromatic number problem
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Which problems have strongly exponential complexity?
- Improved exact algorithms for MAX-SAT
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- An exact algorithm for MAX-CUT in sparse graphs
- A new algorithm for optimal 2-constraint satisfaction and its implications
- New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
- Balanced coloring of bipartite graphs
- New upper bounds for the problem of maximal satisfiability
- A Dynamic Programming Approach to Sequencing Problems
- Set Partitioning via Inclusion-Exclusion
- A new approach to proving upper bounds for MAX-2-SAT
- The Complexity of Satisfiability of Small Depth Circuits
- Applications of a Planar Separator Theorem
- Computing Partitions with Applications to the Knapsack Problem
- Finding a Maximum Independent Set
- Multiplying matrices faster than coppersmith-winograd
- A full derandomization of schöning's k-SAT algorithm
- Some optimal inapproximability results
- Exact Max 2-Sat: Easier and Faster
- MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
- Unnamed Item
