Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time.

Alexander D. Scott Gregory B. Sorkin

Published in: Comb. Probab. Comput. (2006)

Keyphrases

np complete problems
max cut
random instances
np complete
max csp
phase transition
graph coloring
constraint satisfaction
hard problems
constraint satisfaction problems
sat problem
arc consistency
randomly generated
job shop scheduling
decision problems
orders of magnitude
constraint networks
satisfiability problem