36 citations · 170 across the 13 of their papers we have counts for
Showing 2004Show all
2 papers · 1 filter
cond-mat.dis-nn2004★ 8 cited
How much backtracking does it take to color random graphs? Rigorous results on heavy tails
Haixia Jia, Cristopher moore
Many backtracking algorithms exhibit heavy-tailed distributions, in which their running time is often much longer than their median. We analyze the behavior of two natural variants…
cond-mat.dis-nn2004★ 9 cited
The Chromatic Number of Random Regular Graphs
Dimitris Achlioptas, Cristopher Moore
Given any integer d >= 3, let k be the smallest integer such that d < 2k log k. We prove that with high probability the chromatic number of a random d-regular graph is k, k+1, or k…