How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails.

Haixia Jia Cristopher Moore

Published in: CP (2004)

Keyphrases

random graphs
heavy tails
degree distribution
graph theoretic
color images
phase transition
heavy tailed
constraint satisfaction
search algorithm
undirected graph
probability density function
image segmentation
ranking algorithm
power law
small world
random variables
random walk