A NOTE ON OPTICAL ROUTING ON TREES

Bandwidth is a very valuable resource in wavelength division multiplex ed optical networks, The problem of finding an optimal assignment of w avelengths to requests is of fundamental importance in bandwidth utili zation. We present a polynomial-time algorithm for this problem on fix ed constant-size topologies. We combine this algorithm with ideas from Raghavan and Upfal (1994) to obtain an optimal assignment of waveleng ths on constant degree undirected trees, Mihail, Kaklamanis, and Rao ( 1995) posed the following open question: what is the complexity of thi s problem on directed trees? We show that it is NP-complete both on bi nary and constant depth directed trees. (C) 1997 Elsevier Science B.V.