Open access
Date
2002-04Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
In all-optical networks where the technique of wavelength division multiplexing is employed, a connection between two nodes is established by first choosing a route connecting these two nodes and then assigning a wavelength to that route. Many connections can share the same physical link, provided that they use different wavelengths. One technology usually employed in order to make more efficient use of the available bandwidth is that of wavelength converters. A converter is placed in some node of the network and has the ability to alter the transmitting wavelength of any incoming signal. In this paper, we study the problem of placing as few converters as possible in a given network so that the number of necessary wavelengths for any routing is equal to the congestion of the network. This problem is known to be N P-hard even for bidirected graphs. We give a linear time algorithm for directed graphs of bounded treewidth and an FPT algorithm for arbitrary directed graphs. For undirected graphs we show that the problem is solvable optimally in linear time. Show more
Permanent link
https://doi.org/10.3929/ethz-a-004338399Publication status
publishedJournal / series
TIK ReportVolume
Publisher
ETH Zurich, Computer Engineering and Networks LaboratoryEdition / version
Version 1Organisational unit
02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.
More
Show all metadata
ETH Bibliography
yes
Altmetrics