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
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorGODFROY, Quentin
hal.structure.identifierNetworks, Graphs and Algorithms [GANG]
dc.contributor.authorVIENNOT, Laurent
dc.date.accessioned2024-04-15T09:49:26Z
dc.date.available2024-04-15T09:49:26Z
dc.date.issued2010
dc.date.conference2010
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198258
dc.description.abstractCet article concerne des graphes de recouvrement (ci-après nommés {em spanneurs}) qui approximent des multichemins entre des paires de sommets de graphes non orientés de $n$ sommets. Habituellement un spanneur $H$ d'étirement $s$ pour un graphe $G$ est un sous-graphe couvrant tel que la distance dans $H$ entre deux sommets quelconques est au plus $s$ fois la distance dans $G$. Nous étudions ici des spanneurs qui approximent des cycles, et plus généralement $p$ chemins arêtes disjoints avec $p > 1$ pour toute paire de sommets. Pour un graphe $G$ non orienté nous construisons un $3$-spanneur $2$-multichemins avec $O(n^{3/2})$ arêtes. Autrement dit, pour toute paire de sommets $u, v$ la longeur du plus court cycle de $H$ la contenant est au plus le triple de celle dans $G$. On montre que cette construction est optimale en terme d'étirement et de nombre d'arêtes. Dans un second temps il est construit un $(2,8)$-spanneur $2$-multichemins contenant $O(n^{3/2})$ arêtes, ce qui revient à dire que pour toute paire de sommets $u, v$ la longueur du plus court cycle dans $H$ la contenant est au plus du double de celle dans $G$ plus une constante additive de $8$. Pour un $p$ quelconque on observe qu'il existe pour tous entiers $k$ et $p$ un $p(2k-1)$-spanneur $p$-multichemins possédant $O(p cdot n^{1+1/k})$ arêtes, en laissant ouverte la question de savoir s'il est possible à même taille de réduire l'étirement à $2k-1$ pour tout $p > 1$.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isofr
dc.subjectspanneur
dc.subjectdistance
dc.subjectflot
dc.subjectcycle
dc.titleGraphes de recouvrement multichemins
dc.typeCommunication dans un congrès
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.title12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel)
bordeaux.countryFR
bordeaux.conference.cityBelle Dune
bordeaux.peerReviewedoui
hal.identifierinria-00475970
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.organizerMaria Gradinariu Potop-Butucaru and Hervé Rivano
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00475970v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Graphes%20de%20recouvrement%20multichemins&rft.atitle=Graphes%20de%20recouvrement%20multichemins&rft.date=2010&rft.au=GAVOILLE,%20Cyril&GODFROY,%20Quentin&VIENNOT,%20Laurent&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