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 and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover. (C) 2002 Elsevier Science (USA). All rights reserved.
Wavelength rerouting in optical networks, or the Venetian Routing problem / Italiano, Caprara; G., Mohan; Panconesi, Alessandro; Srinivasan,. - In: JOURNAL OF ALGORITHMS. - ISSN 0196-6774. - 45:2(2002), pp. 93-125. [10.1016/s0196-6774(02)00214-6]
Wavelength rerouting in optical networks, or the Venetian Routing problem
PANCONESI, Alessandro;
2002
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 and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover. (C) 2002 Elsevier Science (USA). All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
