Supporting a low delay best-effort class in the presence of real-time traffic

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 $NP$-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