Optimal wavelength routing on directed fiber trees

We present a polynomial-time greedy algorithm that assigns proper wavelengt hs to a set of requests of maximum load L per directed fiber link on a dire cted fiber tree using at most 5/3L wavelengths. This improves previous resu lts of Raghavan and Upfal (Proc. Ann. ACM Symp. on theory of computing STOC , 1994, pp. 134-143), Mihail et al. (Proc. 36th IEEE Symp. on Foundations o f Computer Science, 1995, pp. 548-557), Kaklamanis and Persiano (Proc. Algo rithms - ESA 96, Lecture Notes in Computer Science, 1136, pp. 460-470), Kum ar and Schwabe (Proc. 8th AM. ACM-SIAM Symp. on Discrete Algorithms SODA, 1 997, pp. 437-444). We also prove that no greedy algorithm can in general use less than 5/3L wa velengths for a set of requests of load L in a directed fiber tree, and thu s our algorithm is optimal in the class of greedy algorithms which includes the algorithms presented in [8-10, 12]. (C) 1999 Elsevier Science B.V. All rights reserved.