Chemins disjoints de poids minimum pour la sécurisation de réseaux de télécommunications

David Coudert 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Cette étude s'intèresse à la planification de réseaux de télécommunications tolérants aux pannes. Nous cherchons à établir, pour chaque couple de noeuds du réseau, deux chemins de communication disjoints, l'un étant réservé à la protection de l'autre. Pour un réseau à n noeuds et m liens de communications, nous donnons un algorithme en O(n(m+n log n)), permettant de calculer depuis un noeud donné et vers chacun des autres noeuds deux chemins arc-disjoints dont la somme des poids est minimale. Ceci améliore la complexité des solutions basées sur les algorithmes de flot de poids minimum, qui est en temps O(m(m+n log n) log n) pour un seul couple de sommets.
Type de document :
Communication dans un congrès
3eme Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2001, Saint Jean de Luz, France. pp.47-53, 2001
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00429185
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 16:16:59
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:55:51

Fichier

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

Identifiants

  • HAL Id : inria-00429185, version 1

Collections

Citation

David Coudert. Chemins disjoints de poids minimum pour la sécurisation de réseaux de télécommunications. 3eme Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2001, Saint Jean de Luz, France. pp.47-53, 2001. 〈inria-00429185〉

Partager

Métriques

Consultations de la notice

276

Téléchargements de fichiers

215