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:Inproceedings
Entered by:
TitleApproximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks
Bibtex cite IDRACTI-RU1-2003-61
Booktitle STACS 2004
Series Lecture Notes in Computer Science
Year published 2003
Month March
Volume 2996
Pages 258-269
Publisher Springer Berlin / Heidelberg
DOI 10.1007/b96012
Motivated by the wavelength assignment problem in WDM optical networks, we study path coloring problems in graphs. Given a set of paths P on a graph G, the path coloring problem is to color the paths of P so that no two paths traversing the same edge of G are assigned the same color and the total number of colors used is minimized. The problem has been proved to be NP-hard even for trees and rings. Using optimal solutions to fractional path coloring, a natural relaxation of path coloring, on which we apply a randomized rounding technique combined with existing coloring algorithms, we obtain new upper bounds on the minimum number of colors sufficient to color any set of paths on any graph. The upper bounds are either existential or constructive. The existential upper bounds significantly improve existing ones provided that the cost of the optimal fractional path coloring is sufficiently large and the dilation of the set of paths is small. Our algorithmic results include improved approximation algorithms for path coloring in rings and in bidirected trees. Our results extend to variations of the original path coloring problem arizing in multifiber WDM optical networks.
Caragiannis, Ioannis
Kaklamanis, Christos
fulltext.pdf (main file)
Publication ID607