Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem

Wavelength re-routing has been suggested as a viable and cost effective method to improve the blocking performance of wavelength-routed Wavelength-Division Multiplexing (WDM) networks. In this paper, we prove the computational hardness of this problem even in various special cases, and present several approximation algorithms for its solution.