Skip to Main content Skip to Navigation

A Doubling dimension Threshold $\Theta(\log\log n)$ for augmented graph navigability

Abstract : In his seminal work, Kleinberg showed how to augment meshes using randomedges, so that they become navigable; that is, greedy routing computes pathsof polylogarithmic expected length between any pairs of nodes. This yields thecrucial question of determining wether such an augmentation is possible for allgraphs. In this paper, we answer negatively to this question by exhibiting athreshold on the doubling dimension, above which an infinite family of graphscannot be augmented to become navigable whatever the distribution of randomedges is. Precisely, it was known that graphs of doubling dimension at mostO(log log n) are navigable. We show that for doubling dimension >> log log n,an infinite family of graphs cannot be augmented to become navigable. Finally,we complete our result by studying square meshes, that we prove to always beaugmentable to become navigable.
Document type :
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:23:29 AM
Last modification on : Thursday, November 21, 2019 - 2:38:40 AM


Files produced by the author(s)


  • HAL Id : hal-02102345, version 1



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



Record views


Files downloads