A faster polynomial-space algorithm for Max 2-CSP

DOI10.1016/j.jcss.2015.11.013zbMath1333.68140OpenAlexW2217535067MaRDI QIDQ899585

Keith J. Edwards

Publication date: 30 December 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://discovery.dundee.ac.uk/ws/files/7575590/drd_max2csp_v2.pdf

zbMATH Keywords

Max 2-CSPdeletion depthdeletion-reduction depth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Related Items

$K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs

Cites Work

• 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
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• Upper bounds on the bisection width of 3- and 4-regular graphs
• Pathwidth of cubic graphs and exact algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New exact algorithms for the 2-constraint satisfaction problem
• A \(2^{|E|/4}\)-time algorithm for MAX-CUT
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
• Graph minors. II. Algorithmic aspects of tree-width
• A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
• Automata, Languages and Programming
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques