Please use this identifier to cite or link to this item:
|Title:||Wavelength rerouting in optical networks, or the Venetian Routing problem|
|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. https://doi.org/10.1016/S0196-6774(02)00214-6|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 13, 2017
checked on Dec 8, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.