loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers
Tight Bounds for Wavelength Assignment on Trees of Rings
Denver, Colorado
April 04-April 08
ISBN: 0-7695-2312-9
Zhengbing Bian, Simon Fraser University, Canada
Qian-Ping Gu, Simon Fraser University, Canada
Xiao Zhou, Tohoku University, Japan
Afundamental problem in communication networks is wavelength assignment(WA): given a set of routing paths on a network, assign a wavelength to each path such that the paths with the same wavelength are edge-disjoint, using the minimum number of wavelengths. The WA problem is NP-hard for a tree of rings network which is well used in practice. In this paper, we give an efficient algorithm which solves the WA problem on a tree of rings with an arbitrary (node) degree by at most 3Lwavelengths and achieves an approximation ratio of 2.75 asymptotically, where L is the maximum number of paths on any link in the network. The 3L upper bound is tight that there are instances of theWAproblem that require at least 3L wavelengths even on a tree of rings with degree four. We also give a 3L and 2-approximation algorithm for the WA problem on a tree of rings with degree at most six. Previous results include: 4L (resp. 3L) wavelengths for trees of rings with arbitrary degrees (resp. degree at most eight), and 2-approximation (resp. 2.5-approximation) algorithm for trees of rings with degree four (resp. six).
Index Terms:
Approximation algorithms, communication networks, path coloring, trees of rings, wavelength assignment
Citation:
Zhengbing Bian, Qian-Ping Gu, Xiao Zhou, "Tight Bounds for Wavelength Assignment on Trees of Rings," ipdps, vol. 1, pp.80a, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, 2005
Usage of this product signifies your acceptance of the Terms of Use.