A faster polynomial-space algorithm for Max 2-CSP

DOI10.1016/J.JCSS.2015.11.013zbMATH Open1333.68140OpenAlexW2217535067MaRDI QIDQ899585FDOQ899585

Keith 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

Recommendations

• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
• New exact algorithms for the 2-constraint satisfaction problem
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP

zbMATH Keywords

Max 2-CSPdeletion depthdeletion-reduction depth

Mathematics Subject Classification ID

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

Cites Work

• A partial k-arboretum of graphs with bounded treewidth
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• Graph minors. II. Algorithmic aspects of tree-width
• Upper bounds on the bisection width of 3- and 4-regular graphs
• Pathwidth of cubic graphs and exact algorithms
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
• New exact algorithms for the 2-constraint satisfaction problem
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
• Automata, Languages and Programming
• Title not available (Why is that?)
• A \(2^{|E|/4}\)-time algorithm for MAX-CUT
• Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets

Cited In (3)

• $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP

This page was built for publication: A faster polynomial-space algorithm for Max 2-CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899585)