[clos] Algo DistribuéRésolu/Fermé

Question

Tous les algorithmes distribués que l&#8217;on considèrera ici seront dans le modèle
LOCAL.
On suppose que le graphe G est un cycle orienté muni d&#8217;une m-coloration. Tout sommet
u possède une variable c(u)appartenant {0,. . . ,m-1} représentant la couleur du sommet u. 
L&#8217;orientation est définie en u par les relations prédécesseurs et successeurs, notées respectivement Pred(u) et Succ(u).
Question 1.
Comment on peut  Montrer qu&#8217;en une ronde il est possible de calculer pour G une 4-coloration si m = 6 en donnant l&#8217;algorithme correspondant. 
En déduire qu&#8217;il est possible de calculer
une 3-coloration pour G en partie entier de (1/2 log*m)+ 2 ronds.


cs_Julien39 · Accepted Answer

Salut,

Tu rêves là ! Non nous ne ferons pas cet exercice.

Sujet clos.

[clos] Algo Distribué

1 réponse

Discussions similaires