Skip to Main content Skip to Navigation
Conference papers

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

Cyril Gavoille 1, 2, *
* Corresponding author
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.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00383276
Contributor : Cyril Gavoille <>
Submitted on : Monday, June 1, 2009 - 11:32:11 PM
Last modification on : Tuesday, February 9, 2021 - 3:00:04 PM
Long-term archiving on: : Monday, October 15, 2012 - 10:15:24 AM

File

a.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00383276, version 1

Collections

Citation

Cyril Gavoille. Spanner et routage compact : similarités et différences. AlgoTel, 2009, Carry-Le-Rouet, France. ⟨inria-00383276⟩

Share

Metrics

Record views

288

Files downloads

228