6-coloração de uma árvore de maneira distribuída

Eu tenho algumas dificuldades em entender o algoritmo distribuído para a árvore 6 - colorir no tempo .$O(\log^*n)$

A descrição completa pode ser encontrada no seguinte artigo: Quebra de simetria paralela em gráficos esparsos. Goldberg, Plotkin, Shannon .

Em suma, a ideia é ...

A partir da coloração válida fornecida pelos IDs do processador, o procedimento reduz iterativamente o número de bits nas descrições de cores recolorindo cada nó não raiz com a cor obtida concatenando o índice de um bit no qual difere de e o valor desse bit. A raiz concatena e para formar sua nova cor.$v$$C_v$$C_{parent}(v)$$r$$0$$C_r[0]$

O algoritmo termina após iterações .$O(\log^*n)$

Eu não tenho o entendimento intuitivo de por que ele realmente termina nas iterações $O(\log^*n)$ . Como é mencionado no artigo da iteração final, existe o menor índice em que a string de dois bits difere no máximo 3. Portanto, o bit 0 e o bit 1 podem ser os mesmos e $2^2=4$ , portanto, esse bit 2 nos dará 4 cores + outras 2 cores para o 3º bit diferente, e no total 8 cores e não 6 como no papel, e por que não podemos prosseguir com 2 bits, ainda é possível encontrar bits diferentes e separá-los.

Eu apreciaria uma análise um pouco mais profunda do algoritmo do que no artigo.

No artigo, os autores mencionam que, após as iterações , o número de bits usados ​​para codificar qualquer uma das etiquetas coloridas é no máximo 3. Isso significa que existem no máximo oito cores. Se temos seis ou menos cores, terminamos e, caso contrário, passamos pelo loop mais uma vez.$\log^* n$

Digamos que fazemos uma última iteração de loop. A raiz obtém o rótulo colorido 0 ou 1. Todos os outros nós obtêm um rótulo igual à posição do primeiro bit, onde o rótulo antigo desse nó discorda do rótulo do pai, além de um bit extra. Como na entrada dessa iteração, todas as cores têm três bits de comprimento no pior dos casos, há três posições possíveis em que os bits podem discordar. Portanto, cada nova cor é formada a partir de uma combinação de uma das três opções e um pouco (uma das duas opções); portanto, na saída dessa iteração do loop, existem apenas seis rótulos de cores possíveis; portanto, temos seis cores. O número total de iterações de loop é então$\log^* n + 1 = O(\log^* n)$

Espero que isto ajude!

O algoritmo distribuído para a coloração da árvore 6 no tempo O (log * (n)) é um algoritmo muito bom.

Deixe-me explicar o que é "log * n"

log * (n) - "log Star n", conhecido como "logaritmo iterado"

Em palavras simples, você pode assumir log * (n) = log (log (log (..... (log * (n))))

log * (n) é muito poderoso.

Exemplo:

1) Log * (n) = 5 onde n = Número de átomos no universo

agora sua pergunta:

Por que terminar após o log * n time?

Em cada tamanho redondo do ID reduzido pelo fator de log, o número de cores também é reduzido: para indexar o bit em que dois rótulos de tamanho n bit diferem + 1 mais bit anexado.

Por que apenas 6 cores, por que não mais ou menos?

Por que não 4 cores: {0,1,2,3} - como dois bits são necessários para endereçar o índice onde eles diferem, além de adicionar o “bit de diferença” fornece mais de dois bits.

Por que não 7 cores: {0,1,2,3,4,5,6} - como 7 = 111 (em binário) pode ser descrito com 3 bits e para endereçar o índice (0,1,2) requer dois bits , mais um "bit de diferença" fornece três novamente.

Por que 6 cores? - as cores 110 (para a cor "6") e 111 (para a cor "7") não são necessárias, pois podemos fazer outra rodada! (IDs de três bits podem diferir apenas nas posições 00 (para "0"), 01 (para "1"), 10 (para "2").

você pode reduzir 6 cores para 3 cores , conforme indicado no link acima do seu comentário.