HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073413
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:44:36 PM
Last modification on : Friday, February 4, 2022 - 3:12:35 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:45:45 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

103

Files downloads

147