TY - JOUR T1 - Wavelength rerouting in optical networks, or the Venetian Routing problem JF - Journal of Algorithms Y1 - 2002 A1 - Caprara,Alberto A1 - Italiano,Giuseppe F. A1 - Mohan,G. A1 - Panconesi,Alessandro A1 - Srinivasan, Aravind KW - Approximation algorithms KW - Label Cover KW - Optical networks KW - Shortest paths KW - Wavelength rerouting KW - Wavelength-division multiplexing AB - Wavelength rerouting has been suggested as a viable and cost-effective method to improve the blocking performance of wavelength-routed wavelength-division multiplexing (WDM) networks. This method leads to the following combinatorial optimization problem, dubbed Venetian Routing. Given a directed multigraph G along with two vertices s and t and a collection of pairwise arc-disjoint paths, we wish to find an st-path which arc-intersects the smallest possible number of the given paths. In this paper we prove the computational hardness of this problem even in various special cases, and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover. VL - 45 SN - 0196-6774 UR - http://www.sciencedirect.com/science/article/pii/S0196677402002146 CP - 2 M3 - 10.1016/S0196-6774(02)00214-6 ER -