Graphes de recouvrement multichemins

Cyril Gavoille 1, 2 Quentin Godfroy 1 Laurent Viennot 3
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
3 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Résumé : Cet 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$.
Mots-clés : spanneur distance flot cycle
Type de document :
Communication dans un congrès
12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00475970
Contributeur : Quentin Godfroy <>
Soumis le : vendredi 23 avril 2010 - 13:58:04
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : mardi 28 septembre 2010 - 12:49:07

Fichiers

article_21_04_10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00475970, version 1

Collections

Citation

Cyril Gavoille, Quentin Godfroy, Laurent Viennot. Graphes de recouvrement multichemins. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010. 〈inria-00475970〉

Partager

Métriques

Consultations de la notice

448

Téléchargements de fichiers

500