Max Cut

2008/01/01 by Alantha Newman · 5 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science

paper · doi:10.1007/978-0-387-30162-4_219

published in Encyclopedia of Algorithms, 489-492 (Springer US)

crossref issued 2008/01/01 · crossref published 2008/01/01 · crossref published-print 2008/01/01 · openalex publication_date 2008/01/01 · crossref created 2008/06/26 · openalex created_date 2022/05/12 · crossref deposited 2025/01/30 · crossref indexed 2026/03/11 · openalex updated_date 2026/08/04

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Geometric Approach to Betweenness
• Approximate graph coloring by semidefinite programming
• Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
• On the power of unique 2-prover 1-round games
• Gadgets, Approximation, and Linear Programming
• Reducibility among Combinatorial Problems

Cited by

• Maximum cut [wikipedia]