Approximation Complexity of Nondense Instances of MAX-CUT.

Wenceslas Fernandez de la Vega Marek Karpinski

Published in: Electron. Colloquium Comput. Complex. (2006)

Keyphrases

max cut
np complete problems
np complete
computational complexity
approximation algorithms
graph model
planar graphs
np hard
phase transition
probabilistic model
decision problems
graph coloring