On the Complexity of Distributed Graph Coloring with Local Minimality Constraints
GAVOILLE, Cyril
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
KLASING, Ralf
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
KOSOWSKI, Adrian
Department of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
Voir plus >
Department of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
GAVOILLE, Cyril
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
KLASING, Ralf
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
KOSOWSKI, Adrian
Department of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
Department of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
KUSZNER, Łukasz
Department of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
< Réduire
Department of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
Langue
en
Rapport
Ce document a été publié dans
2007
Résumé en anglais
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 ...Lire la suite >
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.< Réduire
Origine
Importé de halUnités de recherche