6-coloration d'un arbre de manière distribuée

J'ai des difficultés à comprendre l'algorithme distribué pour l'arbre 6 - coloriage $O(\log^*n)$ temps.

La description complète peut être trouvée dans le document suivant: Symétrie symétrique dans les graphes clairsemés. Goldberg, Plotkin, Shannon .

Bref, l'idée est ...

En partant de la coloration valide donnée par les ID de processeur, la procédure réduit de manière itérative le nombre de bits dans les descriptions de couleurs en recolorant chaque nœud non racine $v$ avec la couleur obtenue en concaténant l'indice d'un bit dans lequel $C_v$ diffère de $C_{parent}(v)$et la valeur de ce bit. La racine$r$ concatène $0$ et $C_r[0]$ pour former sa nouvelle couleur.

L'algorithme se termine après $O(\log^*n)$ itérations.

Je n'ai pas la compréhension intuitive pourquoi cela se termine en fait $O(\log^*n)$itérations. Comme il est mentionné dans le document sur l'itération finale, il y a le plus petit index où la chaîne de deux bits diffère est au plus 3. Ainsi, le 0e bit et le 1e bit pourraient être les mêmes et$2^2=4$, donc ces deux bits nous donneront 4 couleurs + 2 autres couleurs pour le 3ème bit différent, et au total 8 couleurs et non 6 comme dans le papier, et pourquoi nous ne pouvons pas continuer avec 2 bits, il est toujours possible de trouver différents bits et sépare les.

J'apprécierais une analyse un peu plus approfondie de l'algorithme que dans l'article.

Dans l'article, les auteurs mentionnent qu'après $\log^* n$itérations, le nombre de bits utilisés pour coder l'une des étiquettes de couleur est au maximum de 3. Cela signifie qu'il y a au plus huit couleurs. Si nous avons six couleurs ou moins, nous avons terminé, sinon nous recommençons la boucle.

Disons que nous faisons une dernière itération de boucle. La racine obtient l'étiquette de couleur 0 ou 1. Chaque autre nœud obtient une étiquette égale à la position du premier bit où l'ancienne étiquette de ce nœud est en désaccord avec l'étiquette de son parent, plus un bit supplémentaire. Étant donné qu'à l'entrée de cette itération, toutes les couleurs ont trois bits de long dans le pire des cas, il y a trois positions possibles où les bits pourraient être en désaccord. Par conséquent, chaque nouvelle couleur est formée d'une combinaison de l'un des trois choix et d'un bit (l'un des deux choix), donc à la sortie de cette itération de boucle, il n'y a que six étiquettes de couleur possibles, nous avons donc six couleurs. Le nombre total d'itérations de boucle est alors$\log^* n + 1 = O(\log^* n)$

J'espère que cela t'aides!

Algorithme distribué pour l'arbre 6 - la coloration en temps O (log * (n)) est un très bon algorithme.

Permettez-moi d'expliquer ce qu'est "log * n"

log * (n) - "log Star n" appelé "Logarithme itéré"

En un mot simple, vous pouvez supposer log * (n) = log (log (log (..... (log * (n)))))

log * (n) est très puissant.

Exemple:

1) Log * (n) = 5 où n = nombre d'atomes dans l'univers

maintenant votre question:

Pourquoi cela se termine-t-il après la connexion * n?

Dans chaque taille ronde de l'ID réduite par le facteur de log, le nombre de couleurs diminue également: pour indexer le bit où deux étiquettes de taille n diffèrent + 1 bit supplémentaire.

Pourquoi seulement 6 couleurs, pourquoi pas plus ou moins?

Pourquoi pas 4 couleurs: {0,1,2,3} - car deux bits sont nécessaires pour adresser l'index là où ils diffèrent, plus l'ajout du "bit de différence" donne plus de deux bits.

Pourquoi pas 7 couleurs: {0,1,2,3,4,5,6} - comme 7 = 111 (en binaire) peut être décrit avec 3 bits, et pour adresser l'index (0,1,2) nécessite deux bits , plus un «bit de différence» donne à nouveau trois.

Pourquoi 6 couleurs? - les couleurs 110 (pour la couleur "6") et 111 (pour la couleur "7") ne sont pas nécessaires, car nous pouvons faire un autre tour! (Les ID de trois bits ne peuvent différer qu'aux positions 00 (pour «0»), 01 (pour «1»), 10 (pour «2»).

vous pouvez réduire de 6 couleurs à 3 couleurs , ce qui est indiqué dans le lien ci-dessus de votre commentaire.