Distributed computing with advice: information sensitivity of graph coloring

FREE-DOWNLOADP Fraigniaud, C Gavoille, D Ilcinkas… – Distributed Computing, 2009 –

Abstract We study the problem of the amount of informa- tion (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 sensitiv- ity of a network problem. A problem is