Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem

TitleWavelength Rerouting in Optical Networks, or the Venetian Routing Problem
Publication TypeBook Chapters
Year of Publication2000
AuthorsCaprara A, Italiano G, Mohan G, Panconesi A, Srinivasan A
EditorJansen K, Khuller S
Book TitleApproximation Algorithms for Combinatorial Optimization
Series TitleLecture Notes in Computer Science
Pagination71 - 84
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-67996-7

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 such paths. In this paper we prove the computational hardness oft his 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.