Mostrar el registro sencillo del ítem

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorGAVOILLE, Cyril
dc.contributor.editorChaintreau
dc.contributor.editorAugustin and Magnien
dc.contributor.editorClémence
dc.date.accessioned2024-04-15T09:51:43Z
dc.date.available2024-04-15T09:51:43Z
dc.date.issued2009
dc.date.conference2009
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198453
dc.description.abstractUn 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.
dc.language.isofr
dc.titleSpanner et routage compact : similarités et différences
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Réseaux et télécommunications [cs.NI]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleAlgoTel
bordeaux.countryFR
bordeaux.conference.cityCarry-Le-Rouet
bordeaux.peerReviewedoui
hal.identifierinria-00383276
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00383276v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Spanner%20et%20routage%20compact%20:%20similarit%C3%A9s%20et%20diff%C3%A9rences&rft.atitle=Spanner%20et%20routage%20compact%20:%20similarit%C3%A9s%20et%20diff%C3%A9rences&rft.date=2009&rft.au=GAVOILLE,%20Cyril&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem