An Optimal Greedy Algorithm for Wavelength Allocation in Directed
Tree Networks
Proceedings of the DIMACS Workshop on Network Design:
Connectivity and Facilities Location, 1997
The problem of allocating wavelengths in optical networks with directed
tree topology has recently received a substantial amount of
attention. Wavelengths must be assigned to connection requests
which are represented as directed paths, and it is required that
paths receive different wavelengths if they share a directed link.
The goal is to minimize the number of different wavelengths used. The
best previously known approximation algorithm for this
NP-hard problem routes any set of paths with
7L/4 wavelengths, where L is the maximum load on a
directed link. We give an improved algorithm that uses at most
5L/3 wavelengths. This is provably the best ratio that
can be achieved by any local greedy algorithm for this problem.
