Fractional Coloring of Bounded Degree Trees

Afonso Ferreira 1 Stéphane Pérennes Hervé Rivano
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We study the dipath-coloring problem in bounded degree and treewidth symmetric digraphs, in which one needs to color the dipaths with a minimum number of colors, in such a way that dipaths using the same arc have different colors. This classic combinatorial problem finds applications in the minimizat- ion of the number of wavelengths in wavelength division multiplexing (WDM) all optical networks. In this paper, we prove that finding an optimal fractional coloring of such dipaths is polynomial. Our solution is constructiv- e, i.e. we give an effective polynomial algorithm for the problem above. We also show some relationships between the integral and fractional problems, prove some polynomial instances of the coloring problem, and derive a $1 + 5/3e$ approximation for the \wdm problem in symmetric directed trees, where $e$ is the classical Neper constant, improving on previous results. Finally we present computational results suggesting that fractional coloring is a good oracle for a branch and bound strategy for coloring dipaths in symmetric directed trees and cycles.
Type de document :
Rapport
RR-4094, INRIA. 2001
Liste complète des métadonnées

https://hal.inria.fr/inria-00072538
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:13:29
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:12:37

Fichiers

Identifiants

  • HAL Id : inria-00072538, version 1

Collections

Citation

Afonso Ferreira, Stéphane Pérennes, Hervé Rivano. Fractional Coloring of Bounded Degree Trees. RR-4094, INRIA. 2001. 〈inria-00072538〉

Partager

Métriques

Consultations de la notice

377

Téléchargements de fichiers

215