Approximability of Paths Coloring Problem in Mesh and Torus Networks
Jérôme Palaysi · Birkhäuser Basel eBooks · 2002
In optical networks, the use of bandwidth can be optimized by a technique called “Wavelength Division Multiplexing” (WDM). In these networks, the data undergo some optical-electronic conversions which make them slow down. To solve this problem, the path was computed and set up before the data transmission: these networks are refered as all-optical networks. Signals can be transmitted through a same fiber link at the same time only if they have different wavelengths. We deal with particular networks families: meshes and toroidal meshes. Let a set of paths assigned to a set of connection requests. We try to find a feasible assignment of wavelengths (called “colors” in our model) to the paths. The goal is to minimize the number of wavelengths used.We show the existence of approximation algorithms for paths computed by a linecolumn routing, while the problem is shown to be no-APX when paths are computed by a free-routing, a shortest-path routing or a minimal load routing.