A Doubling dimension Threshold !(log log n) for augmented graph navigability

Abstract : In his seminal work, Klein leinberg showed how to augment meshes using randoomedges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields thecrucial question of determmining wether such an augmentation is possible for allgraphs. In this his paper, we answer negatively to this question by exhibiting athreshold on the doubling dimension, above which an infinite family of Cayley graphs cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most O(lo log n) are navigable.We show that for do doubling dimension >> log log n, an infinite family of Cayley graphs cannot be augmented to become navigable. Our proof relies on a result of independent interest : we show that the analysis of greedy routing worst performances on graphs augmented by arbitrary distributions of edges can be reduced to the analysis assuming a symmetric distribution. Finally, we complete our result by studying square meshes, that we prove to always be augmentable to become navigable.
Document type :
Reports
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102264
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 10:51:39 AM
Last modification on : Saturday, April 27, 2019 - 1:36:02 AM

File

RR2006-09.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102264, version 1

Collections

Citation

Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker. A Doubling dimension Threshold !(log log n) for augmented graph navigability. [Research Report] LIP RR-2006-09, Laboratoire de l'informatique du parallélisme. 2006, 2+9p. ⟨hal-02102264⟩

Share

Metrics

Record views

7

Files downloads

10