On the Complexity of Distributed Graph Coloring with Local Minimality Constraints

Cyril Gavoille 1, 2 Ralf Klasing 1, 2, * Adrian Kosowski 3 Łukasz Kuszner 3 Alfredo Navarra 4
* Auteur correspondant
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
INRIA Futurs, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : Distributed Greedy Coloring is an interesting and intuitive variation of the standard Coloring problem. Given an order among the colors, a coloring is said to be "greedy" if there does not exist a vertex for which its associated color can be replaced by a color of lower position in the fixed order without violating the property that neighbouring vertices must receive different colors. We consider the problems of "Greedy Coloring" and "Largest First Coloring" (a variant of greedy coloring with strengthened constraints) in the Linial model of distributed computation, providing lower and upper bounds and a comparison to the "$(\Delta+1)$-Coloring" and "Maximal Independent Set" problems, with $\Delta$ being the maximum vertex degree in G.
Type de document :
Rapport
[Research Report] RR-6399, INRIA. 2007
Liste complète des métadonnées

https://hal.inria.fr/inria-00200127
Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 20 décembre 2007 - 16:24:21
Dernière modification le : jeudi 11 janvier 2018 - 06:21:35
Document(s) archivé(s) le : lundi 27 juin 2011 - 17:37:23

Fichiers

RR-6399.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00200127, version 2

Collections

Citation

Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Łukasz Kuszner, Alfredo Navarra. On the Complexity of Distributed Graph Coloring with Local Minimality Constraints. [Research Report] RR-6399, INRIA. 2007. 〈inria-00200127v2〉

Partager

Métriques

Consultations de la notice

386

Téléchargements de fichiers

216