Compact routing and distance oracles for power-law graphs

Christian Sommer (while at MSRA), joint work with Wei Chen, Shanghua Teng, and Yajun Wang

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.

• Technical Report MSR-TR-2009-84
• paper

Talks

• 2008/12/03: Honiden Lab, NII, Tokyo University
• 2008/12/23: Distributed Computing Group, ETH Zurich
• 2009/03/12: ITCS, Tsinghua University
• 2009/05/26: Tokyo University, Group of Prof. Yutaka Matsuo
• 2009/08/05: Center for Nonlinear Studies (CNLS) at Los Alamos National Laboratory (announcement)
• 2009/09/25: 23rd International Symposium on Distributed Computing (DISC) (program)

also: check out our lower bound for distance oracles for sparse graphs

Bibtex

@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 = {Distributed Computing, 23rd International Symposium},
  year      = {2009},
  pages     = {379--391}
}