 |
|
|||
| Authors: | Thomas Erlebach, Klaus Jansen |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | Efficient Implementation of an Optimal Greedy Algorithm for Wavelength Assignment in Directed Tree Networks |
| Year: | 1998 |
| Month: | August |
| Pub-Key: | EJ98a |
| Book Titel: | 2nd Workshop on Algorithm Engineering (WAE 98) |
| Pages: | 13-24 |
| Keywords: | path coloring |
| 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. In this paper the algorithm is 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. The implementation of this efficient version of the algorithm in C++ using the LEDA class library is described, and performance results are reported. |
| Remarks: | Technical Report MPI-I-98-1-019, Max-Planck-Institut für Informatik, Saarbrücken |
| Location: | Saarbrücken |
| Resources: | [BibTeX] |
