research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inbook
Entered by:chita
TitleApproximation Algorithms for Path Coloring in Trees
Bibtex cite IDRACTI-RU1-2006-43
Series The study of the path coloring problem is motivated by the alloc
Year published 2006
Month January
Volume 3484/2006
Pages 74-96
Chapter Efficient Approximation and Online Algorithms
Publisher Springer
Note LNCS 3484
DOI 10.1007/11671541
The study of the path coloring problem is motivated by the allocation of optical bandwidth to communication requests in all-optical networks that utilize Wavelength Division Multiplexing (WDM). WDM technology establishes communication between pairs of network nodes by establishing transmitter-receiver paths and assigning wavelengths to each path so that no two paths going through the same fiber link use the same wavelength. Optical bandwidth is the number of distinct wavelengths. Since state-of-the-art technology allows for a limited number of wavelengths, the engineering problem to be solved is to establish communication minimizing the total number of wavelengths used. This is known as the wavelength routing problem. In the case where the underlying network is a tree, it is equivalent to the path coloring problem. We survey recent advances on the path coloring problem in both undirected and bidirected trees. We present hardness results and lower bounds for the general problem covering also the special case of sets of symmetric paths (corresponding to the important case of symmetric communication). We give an overview of the main ideas of deterministic greedy algorithms and point out their limitations. For bidirected trees, we present recent results about the use of randomization for path coloring and outline approximation algorithms that find path colorings by exploiting fractional path colorings. Also, we discuss upper and lower bounds on the performance of on-line algorithms.
Caragiannis, Ioannis
Kaklamanis, Christos
Persiano, Giuseppe
fulltext.pdf (main file)
Publication ID113