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
Source: 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 14, 2018


checked on Feb 14, 2018

Page view(s)

checked on Feb 11, 2018

Google ScholarTM



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