New exact algorithms for the 2-constraint satisfaction problem (Q2437759): Difference between revisions

@@ Property / describes a project that uses @@
+MAX-2-SAT
@@ Property / describes a project that uses: MAX-2-SAT / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2014.01.010
+Normal rank
@@ Property / OpenAlex ID @@
+W2041669358
@@ Property / OpenAlex ID: W2041669358 / rank @@
+Normal rank
@@ Property / cites work @@
+Large induced degenerate subgraphs
@@ Property / cites work: Large induced degenerate subgraphs / rank @@
+Normal rank
@@ Property / cites work @@
+A new upper bound for Max-2-SAT: A graph-theoretic approach
+Normal rank
@@ Property / cites work @@
+Set Partitioning via Inclusion-Exclusion
@@ Property / cites work: Set Partitioning via Inclusion-Exclusion / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Satisfiability of Small Depth Circuits
+Normal rank
@@ Property / cites work @@
+Improved exact algorithms for MAX-SAT
@@ Property / cites work: Improved exact algorithms for MAX-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+An exact algorithm for MAX-CUT in sparse graphs
@@ Property / cites work: An exact algorithm for MAX-CUT in sparse graphs / rank @@
+Normal rank
@@ Property / cites work @@
+MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
+Normal rank
@@ Property / cites work @@
+Balanced coloring of bipartite graphs
@@ Property / cites work: Balanced coloring of bipartite graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Exact Max 2-Sat: Easier and Faster
@@ Property / cites work: Exact Max 2-Sat: Easier and Faster / rank @@
+Normal rank
@@ Property / cites work @@
+A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
+Normal rank
@@ Property / cites work @@
+New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
+Normal rank
@@ Property / cites work @@
+Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+A Dynamic Programming Approach to Sequencing Problems
+Normal rank
@@ Property / cites work @@
+Q4501522
@@ Property / cites work: Q4501522 / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Partitions with Applications to the Knapsack Problem
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+A new approach to proving upper bounds for MAX-2-SAT
+Normal rank
@@ Property / cites work @@
+New upper bounds for the problem of maximal satisfiability
+Normal rank
@@ Property / cites work @@
+An exact exponential time algorithm for counting bipartite cliques
+Normal rank
@@ Property / cites work @@
+A note on the complexity of the chromatic number problem
+Normal rank
@@ Property / cites work @@
+Applications of a Planar Separator Theorem
@@ Property / cites work: Applications of a Planar Separator Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+A full derandomization of schöning's k-SAT algorithm
+Normal rank
@@ Property / cites work @@
+A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
+Normal rank
@@ Property / cites work @@
+Linear-programming design and analysis of fast algorithms for Max 2-CSP
+Normal rank
@@ Property / cites work @@
+Finding a Maximum Independent Set
@@ Property / cites work: Finding a Maximum Independent Set / rank @@
+Normal rank
@@ Property / cites work @@
+Multiplying matrices faster than coppersmith-winograd
+Normal rank
@@ Property / cites work @@
+A new algorithm for optimal 2-constraint satisfaction and its implications
+Normal rank