| Abstract: |
In all-optical networks with wavelength-division multiplexing several connections can share a physical link if the signals are transmitted on different wavelengths. As the number of available
wavelengths is limited in practice, it is important to find wavelength assignments minimizing the number of different wavelengths used. This path coloring problem is NP-hard, and the best known
polynomial-time approximation algorithm for directed tree networks achieves approximation ratio 5/3, which is optimal in the class of greedy algorithms for this problem. It is shown how the
algorithm can be modified in order to improve its running-time to O(Tec(N,L)) for sets of paths with maximum load L in trees with N nodes, where Tec(n,k) is the time for edge-coloring a k-regular
bipartite graph with n nodes. An implementation of this efficient version of the algorithm in C++ using the LEDA class library is described, and experimental results regarding the running-times
and the number of wavelengths used are reported. An additional heuristic that reduces the number of wavelengths used in the average case while maintaining the worst-case bound of 5L/3 is
described. |
