King Abdulaziz University
The Routing and Spectrum Assignment (RSA) problem has emerged as the key design and control problem in elastic optical networks. In this paper, the authors provide new insight into the Spectrum Assignment (SA) problem in mesh networks by showing that it transforms to the problem of scheduling multiprocessor tasks on dedicated processors. Based on this new perspective, they show that the SA problem in paths is NP-hard for four or more links, but is solvable in polynomial time for three links. They also develop new constant-ratio approximation algorithms for the SA problem in paths when the number of links is fixed.