Liang, WeifaWan, Yingyu2015-12-132015-12-13May 2-6 200302-9743http://hdl.handle.net/1885/84592One limitation of all-optical WDM networks is the wavelength continuity constraint imposed by all-optical cross-connect switches that requires the same wavelength be used on all the links along a path. With random arrivals and departures of connection requests, it happens quite often that a new request has to be blocked due to the fact that there are not enough available resources (e.g. wavelength) to accommodate the request. Wavelength rerouting, a viable and cost-effective method, which rearranges the wavelengths on certain existing routes to free a wavelength continuous route for the new request, has been proposed to improve the blocking probability. In this paper, we study a wavelength rerouting problem in survivable WDM networks as follows. Given a connection request, the problem is to find two link-disjoint paths from the source node to the destination node with an objective to minimize the number of existing routes that have to be wavelength-rerouted. We show that the problem is NP-hard if different wavelengths are assigned to the link-disjoint paths. Otherwise, a polynomial time algorithm is proposed.Keywords: Algorithms; Computational complexity; Cost effectiveness; Optical communication; Optical switches; Polynomials; Problem solving; Telecommunication networks; Wavelength division multiplexing; Cross-connect switches; Polynomial time algorithm; Wavelength re20052015-12-12