Compact routing and distance oracles have been investigated both for general graphs as well as for various graph classes. Many practical networks seem to obey a power law, and, fortunately, general schemes perform quite well for power-law graphs too. In this work, we prove why, using a rigorous average case analysis for random power-law graphs.

	
@inproceedings{conf/disc/ChenSommerTengWang09,
author    = {Wei Chen and Christian Sommer and Shang-Hua Teng and Yajun Wang},
title     = {Compact Routing in Power-law Graphs},
booktitle = {23rd International Symposium on Distributed Computing (DISC)},
year      = {2009},
pages     = {379--391}
}