Please use this identifier to cite or link to this item:
Title: Wavelength rerouting in optical networks, or the Venetian Routing problem
Authors: Caprara, A.
Italiano, G.F.
Mohan, G. 
Panconesi, A.
Srinivasan, A.
Keywords: Approximation algorithms
Label Cover
Optical networks
Shortest paths
Wavelength rerouting
Wavelength-division multiplexing
Issue Date: Nov-2002
Citation: Caprara, A., Italiano, G.F., Mohan, G., Panconesi, A., Srinivasan, A. (2002-11). Wavelength rerouting in optical networks, or the Venetian Routing problem. Journal of Algorithms 45 (2) : 93-125. ScholarBank@NUS Repository.
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 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. © 2002 Elsevier Science (USA). All rights reserved.
Source Title: Journal of Algorithms
ISSN: 01966774
DOI: 10.1016/S0196-6774(02)00214-6
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 20, 2019


checked on Feb 4, 2019

Page view(s)

checked on Dec 15, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.