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:
TitleFractional and Integral Coloring of Locally-Symmetric Sets of Paths on Binary Trees
Bibtex cite IDRACTI-RU1-2003-57
Booktitle Approximation and Online Algorithms
Series Lecture Notes in Computer Science
Year published 2003
Month February
Volume 2909
Pages 325-326
Publisher Springer Berlin / Heidelberg
DOI 10.1007/b95598
Motivated by the problem of allocating optical bandwidth in tree–shaped WDM networks, we study the fractional path coloring problem in trees. We consider the class of locally-symmetric sets of paths on binary trees and prove that any such set of paths has a fractional coloring of cost at most 1.367L, where L denotes the load of the set of paths. Using this result, we obtain a randomized algorithm that colors any locally-symmetric set of paths of load L on a binary tree (with reasonable restrictions on its depth) using at most 1.367L+o(L) colors, with high probability.
Caragiannis, Ioannis
Kaklamanis, Christos
Persianno, P.
Sidiropoulos, A.
fulltext.pdf (main file)
Publication ID603