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

Access Restriction
Open

 Author Fraigniaud, Pierre ♦ Lebhar, Emmanuelle ♦ Lotker, Zvi Source Hyper Articles en Ligne (HAL) Content type Text File Format PDF Language English
 Subject Keyword Small world ♦ Greedy routing ♦ Doubling dimension ♦ Petit monde ♦ Routage glouton ♦ Dimension doublante ♦ info ♦ Computer Science [cs] 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. Educational Use Research Learning Resource Type Report ♦ Article Publisher Date 2006-04-01 Publisher Institution Laboratoire de l'informatique du parallélisme