Thumbnail
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