TY - JOUR

T1 - On the minimum number of wavelengths in multicast trees in WDM networks

AU - Wan, Yingyu

AU - Liang, Weifa

PY - 2005/1

Y1 - 2005/1

N2 - 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.

AB - 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.

KW - Multicast

KW - The minimum number of wavelengths

KW - WDM networks

KW - Wavelength assignment and routing

UR - http://www.scopus.com/inward/record.url?scp=11844269993&partnerID=8YFLogxK

U2 - 10.1002/net.20048

DO - 10.1002/net.20048

M3 - Article

SN - 0028-3045

VL - 45

SP - 42

EP - 48

JO - Networks

JF - Networks

IS - 1

ER -