ABSTRACT
To fix ideas, suppose that an optical network is represented by a directed graph (in many cases a symmetric one) on n vertices, for example, an unidirectional ring ~Cn or a bidirectional ring C∗n. Also provided is a traffic matrix, that is, a family of connection requests represented by a multidigraph I (the number of arcs from i to j corresponding to the number of requests from i to j). An interesting case is when there is exactly one request from i to j; then I = K∗n. Satisfying a request from i to j consists of finding a route (directed path) in G and assigning it a wavelength. The grooming factor, g, means that a request uses only 1/g of the bandwith available on a wavelength along its route. Said otherwise, for each arc e of G and for each wavelength w, there are at most g paths of wavelengths w containing arc e.
