New exact algorithms for the 2-constraint satisfaction problem
From MaRDI portal
(Redirected from Publication:2437759)
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
Cites work
- A Dynamic Programming Approach to Sequencing Problems
- A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A new approach to proving upper bounds for MAX-2-SAT
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- A note on the complexity of the chromatic number problem
- A probabilistic algorithm for k-SAT based on limited local search and restart
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- An exact algorithm for MAX-CUT in sparse graphs
- An exact exponential time algorithm for counting bipartite cliques
- Applications of a Planar Separator Theorem
- Balanced coloring of bipartite graphs
- Computing Partitions with Applications to the Knapsack Problem
- Exact Max 2-Sat: Easier and Faster
- Finding a Maximum Independent Set
- scientific article; zbMATH DE number 1500507 (Why is no real title available?)
- Improved exact algorithms for MAX-SAT
- Large induced degenerate subgraphs
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
- Multiplying matrices faster than coppersmith-winograd
- 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
- Set partitioning via inclusion-exclusion
- Some optimal inapproximability results
- The complexity of satisfiability of small depth circuits
- Which problems have strongly exponential complexity?
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
Cited in
(16)- Improved exact algorithms for mildly sparse instances of MAX SAT
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- 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
- Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
- K₄-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
- 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
- A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
- A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
- A separator theorem for hypergraphs and a CSP-SAT algorithm
- Exact Max 2-Sat: Easier and Faster
- Optimal 2-constraint satisfaction via sum-product algorithms
- A faster polynomial-space algorithm for Max 2-CSP
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)
