A Note on Optical Routing on Trees

Bandwidth is a very valuable resource in wavelength division multiplexed optical networks. The problem of finding an optimal assignment of wavelengths to requests is of fundamental importance in bandwidth utilization. We present a polynomialtime algorithm for this problem on fixed constant-size topologies. We combine this algorithm with ideas from Raghavan and Upfal [15] to obtain an optimal assignment of wavelengths on constant degree undirected trees. Mihail, Kaklamanis, and Rao [14] posed the following open question: what is the complexity of this problem on directed trees? We show that it is NP-complete both on binary and constant depth directed trees. Keywords: Algorithms, Combinatorial Problems, Computational Complexity, Interconnection Networks. 1 Introduction Motivation. Developments in fiber-optic networking technology using Wavelength Division Multiplexing (WDM) have finally reached the point where it 1 Supported by ONR Young Investigator Award N00014-93-1-0590. This work ..