Afficher la notice abrégée

On the Complexity of Distributed Graph Coloring with Local Minimality Constraints

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorGAVOILLE, Cyril
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKLASING, Ralf
hal.structure.identifierDepartment of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
dc.contributor.authorKOSOWSKI, Adrian
hal.structure.identifierDepartment of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
dc.contributor.authorKUSZNER, Łukasz
hal.structure.identifierDipartimento di Matematica e Informatica [Perugia] [DMI]
dc.contributor.authorNAVARRA, Alfredo
dc.date.accessioned2024-04-15T09:56:17Z
dc.date.available2024-04-15T09:56:17Z
dc.date.issued2007
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198819
dc.description.abstractEnDistributed 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.
dc.language.isoen
dc.title.enOn the Complexity of Distributed Graph Coloring with Local Minimality Constraints
dc.typeRapport
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionINRIA
bordeaux.type.reportrr
hal.identifierinria-00200127
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00200127v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2007&rft.au=GAVOILLE,%20Cyril&KLASING,%20Ralf&KOSOWSKI,%20Adrian&KUSZNER,%20%C5%81ukasz&NAVARRA,%20Alfredo&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée