 | The ACM Journal of Experimental Algorithmics |
Volume 4, Article 4, 1999
Efficient Implementation of an Optimal Greedy Algorithm for
Wavelength Assignment in Directed Tree Networks
by
and
http://www.jea.acm.org/1999/ErlebachWavelength/
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 an approximation ratio of 5/3,
which is optimal in the class of greedy algorithms for this problem.
We show 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.
- Keywords: Algorithms, Experimentation,
Path Coloring, Directed Tree Networks, Bipartite Edge Coloring
- CR Categories:
F.2.2 Analysis of Algorithms and Problem Complexity: Nonnumerical Algorithms
and Problems [Computations on discrete structures]
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the article;
this is a small Unix tar file, which includes the source code, a Makefile,
and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
April 1, 1999
|
January 20, 2000
|
March 8, 2000
|
May 10, 2000
|
Last updated and validated May 10, 2000, by editor@jea.acm.org