Optimal Wavelength-Routed Multicasting

Bruno Beauquier 1 Pavol Hell Stéphane Pérennes
1 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Motivated by wavelength division multiplexing in all-optical networks, we consider the problem of finding a set of paths from a fixed source to a multiset of destinations, which can be coloured by the fewest number of colours so that paths of the same colour do not share an arc. We prove that this minimum number of colours is equal to the maximum number of paths that share one arc, minimized over all sets of paths from the source to the destinations. We do this by modeling the problems as network flows in two different networks and relating the structure of their minimum cuts. The problem can be efficiently solved (paths found and coloured) using network flow techniques.
Type de document :
Rapport
RR-3276, INRIA. 1997
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-00073413
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:44:36
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:45:45

Fichiers

Identifiants

  • HAL Id : inria-00073413, version 1

Collections

Citation

Bruno Beauquier, Pavol Hell, Stéphane Pérennes. Optimal Wavelength-Routed Multicasting. RR-3276, INRIA. 1997. 〈inria-00073413〉

Partager

Métriques

Consultations de la notice

181

Téléchargements de fichiers

105