A faster polynomial-space algorithm for Max 2-CSP

DOI10.1016/J.JCSS.2015.11.013MaRDI QIDQ899585zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

Max 2-CSPdeletion depthdeletion-reduction depth

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 714489 (Why is no real title available?)
• A \(2^{|E|/4}\)-time algorithm for MAX-CUT
• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• A partial k-arboretum of graphs with bounded treewidth
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Automata, Languages and Programming
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Graph minors. II. Algorithmic aspects of tree-width
• Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New exact algorithms for the 2-constraint satisfaction problem
• Pathwidth of cubic graphs and exact algorithms
• 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
• Upper bounds on the bisection width of 3- and 4-regular graphs

Cited in

(7)

• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• \(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 universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
• 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
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets

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)