TY - JOUR
T1 - On the minimum number of wavelengths in multicast trees in WDM networks
AU - Wan, Yingyu
AU - Liang, Weifa
N1 - 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.
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. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 42-48 2005.
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. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 42-48 2005.
KW - Multicast
KW - The minimum number of wavelengths
KW - Wavelength assignment and routing
KW - WDM networks
UR - http://www.scopus.com/inward/record.url?scp=11844269993&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-11844269993&origin=recordpage
U2 - 10.1002/net.20048
DO - 10.1002/net.20048
M3 - 21_Publication in refereed journal
VL - 45
SP - 42
EP - 48
JO - Networks
JF - Networks
SN - 0028-3045
IS - 1
ER -