s'authentifier
version française rss feed

inria-00383276, version 1

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

Cyril Gavoille (Auteur à contacter de préférence) a12

AlgoTel (2009)

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.

  • a –  Université Sciences et Technologies - Bordeaux I
  • 1 :  Laboratoire Bordelais de Recherche en Informatique (LaBRI)
  • CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
  • 2 :  CEPAGE (INRIA Bordeaux - Sud-Ouest)
  • INRIA – CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
  • Domaine : Informatique/Algorithme et structure de données
    Informatique/Réseaux et télécommunications
 
  • inria-00383276, version 1
  • oai:hal.inria.fr:inria-00383276
  • Contributeur : 
  • Soumis le : Lundi 1 Juin 2009, 23:32:11
  • Dernière modification le : Mardi 2 Juin 2009, 08:33:49
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...