Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00429185
Contributor : David Coudert <>
Submitted on : Sunday, November 1, 2009 - 4:16:59 PM
Last modification on : Monday, October 12, 2020 - 10:30:12 AM
Long-term archiving on: : Thursday, June 17, 2010 - 6:55:51 PM

File

dcoudert_papier20.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00429185⟩

Share

Metrics

Record views

305

Files downloads

406