An Optimal Greedy Algorithm for Wavelength Allocation in Directed Tree Networks

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
$\mathcal{NP}$--hard problem routes any set of paths with
$\frac{7}{4}L$ wavelengths, where $L$ is the maximum load on a
directed link. We give an improved algorithm that uses at most
$\frac{5}{3}L$ wavelengths. This is provably the best ratio that
can be achieved by any local greedy algorithm for this problem.

Joint work with Thomas Erlebach, Christos Kaklamanis and Pino Persiano