36 citations · 170 across the 13 of their papers we have counts for
Showing cond-mat.dis-nnShow all
3 papers · 1 filter
cond-mat.dis-nn2005★ 35 cited
On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs
Dimitris Achlioptas, Aaron Clauset, David Kempe +1
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtainin…
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…