ALCOMFT-TR-01-54

Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes and Herve Rivano
Fractional Path Coloring with Applications to WDM Networks
Patras. Work package 2. May 2001.

Abstract: This paper addresses the natural relaxation of the path coloring problem, in which one needs to color directed paths on a symmetric directed graph with a minimum number of colors, in such a way that paths using the same arc of the graph have different colors. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (WDM) all-optical networks.

Postscript file: ALCOMFT-TR-01-54.ps.gz (74 kb).