@article{01c116d83ae54366b978cb3e6c1cd164, title = "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. {\textcopyright} 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 42-48 2005.", keywords = "Multicast, The minimum number of wavelengths, Wavelength assignment and routing, WDM networks", author = "Yingyu Wan and Weifa Liang", note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to lbscholars@cityu.edu.hk.", year = "2005", month = jan, doi = "10.1002/net.20048", language = "English", volume = "45", pages = "42--48", journal = "Networks", issn = "0028-3045", publisher = "John Wiley & Sons, Inc.", number = "1", }