FRAIGNIAUD, Pierre; GAVOILLE, Cyril; ILCINKAS, David; PELC, Andrzej

doi:10.1007/s00446-008-0076-y

Metadatos

Licencia de uso del documento

FRAIGNIAUD, Pierre
Laboratoire d'informatique Algorithmique : Fondements et Applications [LIAFA]

GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

Idioma

Article de revue

Este ítem está publicado en

Distributed Computing. 2009-03, vol. 21, n° 6, p. 395-403

Springer Verlag

Resumen en inglés

We 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.< Leer menos

Palabras clave en inglés

network algorithm

graph coloring

distributed computing

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198443

DOI

http://dx.doi.org/10.1007/s00446-008-0076-y

Proyecto ANR

Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800