Spanner et routage compact : similarités et différences

Cyril Gavoille 1, 2, *
* Auteur correspondant
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Résumé : Un spanner est un sous-graphe $H$ couvrant les sommets d'un graphe $G$ et qui approxime les distances de $G$. L'étirement de $H$ est borné par une fonction $s$, on parle alors de $s$-spanner, si $d_H(u,v) \le s(d_G(u,v))$ pour tous sommets $u,v$ de $G$. De nombreux travaux concernent l'étude du compromis entre la taille du spanner (\cad son nombre d'arêtes) et son étirement. En parallèle, le routage compact s'intéresse à la construction de schémas de routage réalisant un compromis entre la taille des tables de routage et l'étirement de la longueur des routes générées. Il se trouve que le compromis taille-étirement pour les spanners et pour les schémas de routage coïncide\footnote{Pour être plus précis c'est le degré moyen des spanners qui coïncide avec la taille des tables.} pour les étirements \emph{multiplicatifs}, \cad lorsque $s(d) = \alpha \cdot d$ pour une constante $\alpha \ge 1$. Des travaux récents montrent qu'il est possible de construire des $s$-spanners de taille comparables aux précédents mais avec un étirement \emph{additif}, $s(d) = d + \beta$ pour une constante $\beta \ge 0$. Nous montrons que les résultats concernant les spanners d'étirement additifs ne peuvent pas être étendus au routage compact. Plus précisément nous montrons que tout schéma de routage garantissant pour tout graphe à $n$ sommets des tables de routage de taille en $o(\sqrt{n}\,)$ possède un étirement additif non borné. Cette borne inférieure prouve pour la première fois une séparation entre les deux théories.
Type de document :
Communication dans un congrès
Chaintreau, Augustin and Magnien, Clémence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00383276
Contributeur : Cyril Gavoille <>
Soumis le : lundi 1 juin 2009 - 23:32:11
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : lundi 15 octobre 2012 - 10:15:24

Fichier

a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00383276, version 1

Citation

Cyril Gavoille. Spanner et routage compact : similarités et différences. Chaintreau, Augustin and Magnien, Clémence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009. 〈inria-00383276〉

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

121