ALCOMFT-TR-01-29

Alberto Caprara, Giuseppe F. Italiano, G. Mohan, Alessandro Panconesi and Aravind Srinivasan
Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem
Rome. Work packages 2 and 4. March 2001.

Abstract: 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 vertcies s and t and a collectoin 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 variuos special cases, and present several approximation algorithms for its solution. In particular, we show a non-trivial connection between Venetian Routing and Label Cover.

Postscript file: ALCOMFT-TR-01-29.ps.gz (168 kb).