The MAX-CUT of sparse random graphs.
Hervé DaudéConrado MartínezVonjy RasendrahasinaVlady RavelomananaPublished in: SODA (2012)
Keyphrases
- random graphs
- max cut
- phase transition
- np complete problems
- graph theoretic
- planar graphs
- undirected graph
- np hard
- graph model
- np complete
- graph partitioning
- small world
- spectral graph
- power law
- combinatorial problems
- image processing
- ranking algorithm
- min max
- constraint satisfaction
- graph coloring
- probability distribution
- high dimensional
- multiscale