Title :
A Fixed-Parameter Tractable Approach for the Wavelength Assignment Problem in Transparent Networks
Author :
Drummond, Andre C. ; Fonseca, Nelson L S da
Author_Institution :
Inst. of Comput., State Univ. of Campinas, Campinas
fDate :
7/1/2008 12:00:00 AM
Abstract :
One possibility for the formulation of the RWA problem in transparent networks is the creation of an auxiliary undirected graph with vertices representing lightpaths in the network. Coloring graphs is an NP-hard problem and various heuristics have been proposed for the solution of wavelength assignment problem in optical networks. This letter introduces an approach for exact solution for the assignment of wavelengths to lightpaths in transparent networks using a novel parameterized complexity theory.
Keywords :
optical fibre networks; telecommunication network routing; wavelength assignment; wavelength division multiplexing; NP-hard problem; RWA problem; fixed-parameter tractable approach; parameterized complexity theory; transparent networks; wavelength assignment problem; Complexity theory; Costs; Helium; NP-hard problem; Network topology; Optical fiber networks; Optical wavelength conversion; WDM networks; Wavelength assignment; Wavelength routing;
Journal_Title :
Communications Letters, IEEE
DOI :
10.1109/LCOMM.2008.080450
