The Phase Transition in Multitype Binomial Random Graphs.

Mihyun Kang Christoph Koch Angélica Pachón

Published in: SIAM J. Discret. Math. (2015)

Keyphrases

random graphs
phase transition
constraint satisfaction
satisfiability problem
randomly generated
hard problems
np complete
graph coloring
random constraint satisfaction problems
cellular automata
np complete problems
probability distribution
random instances
lower bound
sat problem
random sat