Lecture Notes in Computer Science, vol. 3480, pp. 448-458, May 2005 (SCI, IF 0.402)
Zhanna Olmes, Kun Myon Choi, Min Young Chung, Tae-Jin Lee, and Hyunseung Choo
Among many solutions to Routing and Wavelength Assignment (RWA) problems based on Edge Disjoint Paths (EDP), the Path Conflict Graph (PCG) algorithm shows outstanding performance in terms of wavelength. In this paper, we improve the PCG algorithm by imposing limitations on the EDPs length based on the fact that the EDPs are longer than the average length for the rarely selected demands. We conclude that the running time of the PCG algorithm can be reduced by half even in the worst case scenario while expending fewer wavelengths than or equal to that of the BGAforEDP and MAX_EDP algorithms by using the proposed PCG approximation technique.