MAX k‐CUT and approximating the chromatic number of random graphs

DOI10.1002/rsa.20096zbMath1094.68118OpenAlexW4247919263MaRDI QIDQ5471049

Moore, Cristopher, Vishal Sanwalani, Amin Coja-Oghlan

Publication date: 6 June 2006

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20096

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex degrees (05C07)

Related Items (9)

On the maximal cut in a random hypergraph ⋮ An improved algorithm for approximating the chromatic number of \(G_{n,p}\) ⋮ Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ A class of spectral bounds for max \(k\)-cut ⋮ MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems ⋮ Typical performance of approximation algorithms for NP-hard problems ⋮ Approximability Distance in the Space of H-Colourability Problems ⋮ Unnamed Item ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs

Uses Software

• Outward rotations

Cites Work

• Geometric algorithms and combinatorial optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Some optimal inapproximability results
• Automata, Languages and Programming
• The two possible values of the chromatic number of a random graph
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: MAX k‐CUT and approximating the chromatic number of random graphs