Skip to Main content Skip to Navigation

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 , Laboratoire I3S - 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.
Document type :
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 12:44:36 PM
Last modification on : Monday, October 12, 2020 - 10:30:26 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:45:45 PM


  • HAL Id : inria-00073413, version 1



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



Record views


Files downloads