## Abstract

The routing and spectrum assignment problem has emerged as the key design and control problem in elastic optical networks. In this work, we show that the spectrum assignment (SA) problem in mesh networks transforms to the problem of scheduling multiprocessor tasks on dedicated processors. Based on this new perspective, we show that the SA problem in chain (linear) networks is NP-hard for four or more links, but is solvable in polynomial time for three links. We also develop new constant-ratio approximation algorithms for the SA problem in chains when the number of links is fixed. Finally, we present several list scheduling algorithms that are computationally efficient and simple to implement, yet produce solutions that, on average, are within 1%–5% of the lower bound.

© 2014 Optical Society of America

Full Article | PDF Article**More Like This**

Sahar Talebi and George N. Rouskas

J. Opt. Commun. Netw. **9**(5) 456-465 (2017)

Ching-Fang Hsu, Yuan-Chih Chang, and Siou-Ci Sie

J. Opt. Commun. Netw. **8**(7) 507-520 (2016)

Xiong Wang, Kaixuan Kuang, Sheng Wang, Shizhong Xu, Hong Liu, and Gordon Ning Liu

J. Opt. Commun. Netw. **6**(12) 1115-1127 (2014)