A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
DOI10.1007/S00453-014-9883-7zbMATH Open1328.68089OpenAlexW2074729689MaRDI QIDQ494789FDOQ494789
Authors: Keith Edwards, Eric J. McDermid 
Publication date: 2 September 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://discovery.dundee.ac.uk/en/publications/c1d55881-e676-417d-b89a-43480fd4f770
Recommendations
- Complexity and approximability of parameterized MAX-CSPs
- Complexity and Approximability of Parameterized MAX-CSPs
- Approximating a generalization of MAX 2SAT and MIN 2SAT
- A faster polynomial-space algorithm for Max 2-CSP
- CSP duality and trees of bounded pathwidth
- On regularity of Max-CSPs and Min-CSPs
- The approximability of MAX CSP with fixed-value constraints
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- Approximating dense MAX 2-CSPs
- The parameterized complexity of maximality and minimality problems
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)
Cites Work
- Title not available (Why is that?)
- A measure & conquer approach for the analysis of exact algorithms
- Title not available (Why is that?)
- Exact exponential algorithms.
- A partial k-arboretum of graphs with bounded treewidth
- On two techniques of combining branching and treewidth
- Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
- Fragmentability of graphs
- Topics in structural graph theory
- Pathwidth of cubic graphs and exact algorithms
- Open problems around exact algorithms
- Forbidden minors characterization of partial 3-trees
- 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
- New Bounds for MAX-SAT by Clause Learning
- A new approach to proving upper bounds for MAX-2-SAT
- A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
- New Upper Bounds for Maximum Satisfiability
- Title not available (Why is that?)
- Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
- New exact algorithms for the 2-constraint satisfaction problem
- An exact algorithm for MAX-CUT in sparse graphs
- Exact Algorithms for Maximum Independent Set
- New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
- Title not available (Why is that?)
- Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
- A bound on the pathwidth of sparse graphs with applications to exact algorithms
- Maximum acyclic and fragmented sets in regular graphs
- Automata, Languages and Programming
Cited In (5)
- A bound on the pathwidth of sparse graphs with applications to exact algorithms
- $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
- A faster polynomial-space algorithm for Max 2-CSP
- Pathwidth of cubic graphs and exact algorithms
Uses Software
This page was built for publication: A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494789)
