Sur la difficulté de séparer un graphe par des plus courts chemins

Emilie Diot 1, 2 Cyril Gavoille 1, 2, 3 Pascal Ochem 4
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
Résumé : Les schémas de routage et de calcul de distances les plus efficaces sont conçus à partir de décompositions hiérarchiques de la topologie en plus courts chemins. Ces constructions sont calculables efficacement pour de nombreuses topologies, comme les graphes planaires par exemple. Dans cet article nous montrons cependant que la décomposition d'une topologie arbitraire en $k$ plus courts chemins est NP-complet.
Type de document :
Communication dans un congrès
Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2011, Cap Estérel, France. 2011
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00588312
Contributeur : Cyril Gavoille <>
Soumis le : vendredi 22 avril 2011 - 18:11:38
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : jeudi 8 novembre 2012 - 17:15:16

Fichier

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

Identifiants

  • HAL Id : inria-00588312, version 1

Citation

Emilie Diot, Cyril Gavoille, Pascal Ochem. Sur la difficulté de séparer un graphe par des plus courts chemins. Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2011, Cap Estérel, France. 2011. 〈inria-00588312〉

Partager

Métriques

Consultations de la notice

292

Téléchargements de fichiers

173