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

Description

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.

Abstract

National audience

Additional details