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

Abstract

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.