Mostrar el registro sencillo del ítem

Distributed computing with advice: information sensitivity of graph coloring

hal.structure.identifierLaboratoire d'informatique Algorithmique : Fondements et Applications [LIAFA]
dc.contributor.authorFRAIGNIAUD, Pierre
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorGAVOILLE, Cyril
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorILCINKAS, David
hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorPELC, Andrzej
dc.date.accessioned2024-04-15T09:51:36Z
dc.date.available2024-04-15T09:51:36Z
dc.date.issued2009-03
dc.identifier.issn0178-2770
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198443
dc.description.abstractEnWe study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Verlag
dc.subject.ennetwork algorithm
dc.subject.engraph coloring
dc.subject.endistributed computing
dc.title.enDistributed computing with advice: information sensitivity of graph coloring
dc.typeArticle de revue
dc.identifier.doi10.1007/s00446-008-0076-y
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.journalDistributed Computing
bordeaux.page395-403
bordeaux.volume21
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue6
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00395775
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00395775v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Distributed%20Computing&rft.date=2009-03&rft.volume=21&rft.issue=6&rft.spage=395-403&rft.epage=395-403&rft.eissn=0178-2770&rft.issn=0178-2770&rft.au=FRAIGNIAUD,%20Pierre&GAVOILLE,%20Cyril&ILCINKAS,%20David&PELC,%20Andrzej&rft.genre=article


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem