On the Complexity of Distributed Graph Coloring with Local Minimality Constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

On the Complexity of Distributed Graph Coloring with Local Minimality Constraints

Résumé

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.
Fichier principal
Vignette du fichier
RR-6399.pdf (347.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00200127 , version 1 (20-12-2007)
inria-00200127 , version 2 (20-12-2007)

Identifiants

  • HAL Id : inria-00200127 , version 2

Citer

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⟩
236 Consultations
334 Téléchargements

Partager

Gmail Facebook X LinkedIn More