The Phase Transition and Connectedness in Uniformly Grown Random Graphs.

Béla Bollobás Oliver Riordan

Published in: WAW (2004)

Keyphrases

random graphs
phase transition
constraint satisfaction
satisfiability problem
np complete
hard problems
randomly generated
random constraint satisfaction problems
random instances
sat problem
graph coloring
cellular automata
np complete problems
connected components
orders of magnitude
special case
social networks