### Efficient implementation of an optimal greedy algorithm for wavelength assignment in directed tree networksEfficient implementation of an optimal greedy algorithm for wavelength assignment in directed tree networks

Access Restriction
Subscribed

 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

Source: ACM Digital Library