ALCOMFT-TR-03-167

Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano and Anastasios Sidiropoulos
Fractional and Integral Coloring of Locally-Symmetric Sets of Paths on Binary Trees
Patras. Work packages 2 and 4. December 2003.

Abstract: 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.

Postscript file: ALCOMFT-TR-03-167.ps.gz (232 kb).