Complexity of Converter Placement Supporting Broadcast in WDM Networks

Wavelength converters simplify the wavelength assignment problem in virtual topology design in optical networks and increase the utilization of the fiber bandwidth. However, converters are costly, and minimizing the number of converters needed to support a given level of functionality has been investigated in the literature in various contexts. In particular, previous work has addressed the problem of minimizing the number of converters needed to support broadcast over all network nodes with a given set of residual wavelengths on each link. In this paper, we show that previous work leaves the computational complexity of this question open. We go on to show that the problem is in fact NP-complete, but becomes tractable in the special case when the network graph is a tree. We also show that there are cases when the heuristics articulated in previous work fail to provide solutions, and provide some heuristic approaches to solve the general problem.