A Doubling dimension Threshold $\Theta(\log\log n)$ for augmented graph navigability
Résumé
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.
Kleinberg a montré comment augmenter les grilles par des liens aléeatoires defaçcon à ce qu'elles deviennent navigables; c'est-à-dire que le routage gloutoncalcule des chemins de longueur polylogarithmique en espérance entre toutepaire de noeuds. Cela conduit à la question cruciale de déterminer si une telleaugmentation est possible pour tout graphe. Dans cet article, nous répondonsnégativement à cette question en exhibant un seuil sur la dimension doublante,au-dessus duquel une famille infinie de graphes ne peut pas être augmentéepour devenir navigable, quelle que soit la distribution de liens. Précisément, ilétait connu que les graphes de dimension doublante au plus O(log log n) sontnavigable. Nous montrons que pour une dimension doublante >> log log n, unefamille infinie de graphes ne peut être augmentée pour devenir navigable. Enfin,nous complétons notre résultat en étudiant les grilles que nous démontronspouvoir toujours être augmentées pour devenir navigables.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...