On the Minimum Number of Wavelengths in Multicast Trees in WDM Networks

Abstract

We consider the problem of minimizing the number of wavelengths needed to connect a given multicast set in a multihop WDM optical network. This problem was introduced and studied by Li et al. (Networks, 35(4), 260-265, 2000) who showed that it is NP-complete. They also presented an approximation algorithm for which they claimed an approximation ratio of c(1 +2 log Δ), where c is the maximum number of connected components in the subgraph induced by any wavelength and A is the maximum number of nodes in any connected component induced by any wavelength. In this article we present an example demonstrating that their claim cannot be correct-the approximation ratio is Ω(n), even though the subgraph induced by every wavelength is connected, where n is the number of nodes in the network. In fact, we show that the problem cannot be approximated within O(2log1/2-ε) unless NP ⊆ DTIME(n poly log n) for any constant E > 0, where m is the number of edges in the network. We complement this hardness result by presenting a polynomial-time algorithm with an approximation ratio of (1 + In 3 + 2 log Δ) when the subgraph induced by every wavelength is connected, and an approximation ratio of O(√(n log Δ)/opt) in the general case, where opt is the number of wavelengths used in an optimal solution and 1 ≤ opt ≤ n - 1.