Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold.

Alexis C. Kaporis Lefteris M. Kirousis Elias C. Stavropoulos

Published in: ESA (2006)

Keyphrases

max cut
np complete problems
np complete
graph coloring
graph model
randomly generated
planar graphs
graph partitioning
np hard
satisfiability problem
sat problem
hard problems
phase transition
spectral graph
multiscale
clustering algorithm
temporal logic