A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
From MaRDI portal
Publication:494789
DOI10.1007/s00453-014-9883-7zbMath1328.68089OpenAlexW2074729689MaRDI QIDQ494789
Keith J. 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
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
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 ⋮ $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
- Exact exponential algorithms.
- Forbidden minors characterization of partial 3-trees
- On two techniques of combining branching and treewidth
- Pathwidth of cubic graphs and exact algorithms
- A partial k-arboretum of graphs with bounded treewidth
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Fragmentability of graphs
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- New exact algorithms for the 2-constraint satisfaction problem
- An exact algorithm for MAX-CUT in sparse graphs
- Open problems around exact algorithms
- Exact Algorithms for Maximum Independent Set
- New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
- Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
- A measure & conquer approach for the analysis of exact algorithms
- 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
- 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
This page was built for publication: A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
