A \(2^{|E|/4}\)-time algorithm for MAX-CUT

DOI10.1007/s10958-005-0101-7zbMath1093.90070OpenAlexW2000579976MaRDI QIDQ2577592

Alexander S. Kulikov, S. S. Fedin

Publication date: 3 January 2006

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-005-0101-7

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

A faster polynomial-space algorithm for Max 2-CSP ⋮ Open problems around exact algorithms ⋮ Pathwidth of cubic graphs and exact algorithms ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Algorithms for Sat and upper bounds on their complexity
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

This page was built for publication: A \(2^{|E|/4}\)-time algorithm for MAX-CUT