A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP (Q494789): Difference between revisions

@@ Property / DOI @@
-.1007/s00453-014-9883-7
@@ Property / DOI: 10.1007/s00453-014-9883-7 / rank @@
-Normal rank
@@ Property / author @@
-Keith J. Edwards
@@ Property / author: Keith J. Edwards / rank @@
-Normal rank
@@ Property / author @@
-Eric J. McDermid
@@ Property / author: Eric J. McDermid / rank @@
-Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C38
@@ Property / Mathematics Subject Classification ID: 05C38 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C85
@@ Property / Mathematics Subject Classification ID: 05C85 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q17
@@ Property / Mathematics Subject Classification ID: 68Q17 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6477662
@@ Property / zbMATH DE Number: 6477662 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+constraint satisfaction problems
@@ Property / zbMATH Keywords: constraint satisfaction problems / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+Max 2-CSP
@@ Property / zbMATH Keywords: Max 2-CSP / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+treewidth
@@ Property / zbMATH Keywords: treewidth / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+pathwidth
@@ Property / zbMATH Keywords: pathwidth / rank @@
+Normal rank
@@ Property / author @@
+Keith J. Edwards
@@ Property / author: Keith J. Edwards / rank @@
+Normal rank
@@ Property / author @@
+Eric J. McDermid
@@ Property / author: Eric J. McDermid / rank @@
+Normal rank
@@ 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 / OpenAlex ID @@
+W2074729689
@@ Property / OpenAlex ID: W2074729689 / rank @@
+Normal rank
@@ Property / cites work @@
+Forbidden minors characterization of partial 3-trees
+Normal rank
@@ Property / cites work @@
+Q4511230
@@ Property / cites work: Q4511230 / rank @@
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
+Normal rank
@@ Property / cites work @@
+Q3043707
@@ Property / cites work: Q3043707 / 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 @@
+Fragmentability of graphs
@@ Property / cites work: Fragmentability of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
+Normal rank
@@ Property / cites work @@
+Q2911581
@@ Property / cites work: Q2911581 / rank @@
+Normal rank
@@ Property / cites work @@
+On two techniques of combining branching and treewidth
+Normal rank
@@ Property / cites work @@
+A measure &amp; conquer approach for the analysis of exact algorithms
+Normal rank
@@ Property / cites work @@
+Pathwidth of cubic graphs and exact algorithms
@@ Property / cites work: Pathwidth of cubic graphs and exact algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Exact exponential algorithms.
@@ Property / cites work: Exact exponential algorithms. / 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 @@
+New exact algorithms for the 2-constraint satisfaction problem
+Normal rank
@@ Property / cites work @@
+Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
+Normal rank
@@ Property / cites work @@
+Maximum acyclic and fragmented sets in regular graphs
+Normal rank
@@ Property / cites work @@
+Q4501522
@@ Property / cites work: Q4501522 / rank @@
+Normal rank
@@ Property / cites work @@
+A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
+Normal rank
@@ Property / cites work @@
+A new approach to proving upper bounds for MAX-2-SAT
+Normal rank
@@ Property / cites work @@
+New Bounds for MAX-SAT by Clause Learning
@@ Property / cites work: New Bounds for MAX-SAT by Clause Learning / rank @@
+Normal rank
@@ Property / cites work @@
+New Upper Bounds for Maximum Satisfiability
@@ Property / cites work: New Upper Bounds for Maximum Satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
+Normal rank
@@ Property / cites work @@
+Linear-programming design and analysis of fast algorithms for Max 2-CSP
+Normal rank
@@ Property / cites work @@
+Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Q4414647
@@ Property / cites work: Q4414647 / rank @@
+Normal rank
@@ Property / cites work @@
+Open problems around exact algorithms
@@ Property / cites work: Open problems around exact algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Exact Algorithms for Maximum Independent Set
@@ Property / cites work: Exact Algorithms for Maximum Independent Set / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S00453-014-9883-7
@@ Property / DOI: 10.1007/S00453-014-9883-7 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:494789