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 :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02102345
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:23:29 AM
Last modification on : Thursday, April 25, 2019 - 5:21:06 PM

File

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

Identifiers

  • HAL Id : hal-02102345, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

9

Files downloads

15