2.2k citations · 3.4k across the 40 of their papers we have counts for
4 papers · 2 filters
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…
Accuracy and Scaling Phenomena in Internet Mapping
Aaron Clauset, Cristopher Moore
A great deal of effort has been spent measuring topological features of the Internet. However, it was recently argued that sampling based on taking paths or traceroutes through the…
Why Mapping the Internet is Hard
Aaron Clauset, Cristopher Moore
Despite great effort spent measuring topological features of large networks like the Internet, it was recently argued that sampling based on taking paths through the network (e.g.,…
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…