Access Restriction

Author Erlebach, T. ♦ Jansen, K.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Algorithms ♦ Bipartite edge coloring ♦ Directed tree networks ♦ Experimentation ♦ 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 $\textit{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 $\textit{O(Tec(N,L))}$ for sets of paths with maximum load $\textit{L}$ in trees with $\textit{N}$ nodes, where Tec(n, k) is the time for edge-coloring a $\textit{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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 4

Open content in new tab

   Open content in new tab
Source: ACM Digital Library