Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time.

The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse Graphs. Goldberg, Plotkin, Shannon.

In short, the idea is ...

Starting from the valid coloring given by the processor ID's, the procedure iteratively reduces the number of bits in the color descriptions by recoloring each nonroot node $v$ with the color obtained by concatenating the index of a bit in which $C_v$ differs from $C_{parent}(v)$ and the value of this bit. The root $r$ concatenates $0$ and $C_r[0]$ to form its new color.

The algorithm terminates after $O(\log^*n)$ iterations.

I don' have the intuitive understanding why it's actually terminates in $O(\log^*n)$ iterations. As it's mentioned in the paper on the final iteration there is the smallest index where two bit string differs is at most 3. So 0th bit and 1th bit could be the same and $2^2=4$, so this two bit will give us 4 colors + another 2 colors for different 3th bit, and in total 8 colors and not 6 like in the paper, and why we cannot proceed further with 2 bits, it's still possible to find different bits and separate them.

I would appreciate a little bit deeper analysis of the algorithm than in the paper.

share|improve this question
1  
These might help: Section 5.3.4 of cs.helsinki.fi/u/josuomel/dda and p. 178– of cs.helsinki.fi/u/josuomel/dda-2012/dda-lectures.pdf –  Jukka Suomela Feb 6 '13 at 11:23
    
@JukkaSuomela, thank you very much, really good lecture notes. One minor point, in lecture notes Coloring, page 11 I found that colors 11* is never chosen, but why, what the reason? –  fog Feb 6 '13 at 16:36

1 Answer 1

Distributed Algorithm for tree 6 - coloring in O(log* (n)) time is very good algorithm.

Let me explain what is "log* n"

log* (n)- "log Star n" as known as "Iterated logarithm"

In simple word you can assume log* (n)= log(log(log(.....(log* (n))))

log* (n) is very powerful.

Example:

1) Log* (n)=5 where n= Number of atom in universe

now your question:

Why it terminate after log*n time?

In each round size of the ID reduced by log factor hence the number of color is also reducing: to index bit where two label of size n bit differ + 1 more appending bit.

Why only 6 colors, why not More or Less?

Why not 4 colors: {0,1,2,3} - as two bits are required to address index where they differ, plus adding the “difference-bit“ gives more than two bits.

Why not 7 colors: {0,1,2,3,4,5,6} - as 7=111 (in Binary) can be described with 3 bits, and to address index (0,1,2) requires two bits, plus one “difference-bit“ gives three again.

Why 6 Colors?- colors 110 (for color “6“) and 111 (for color “7“) are not needed, as we can do another round! (IDs of three bits can only differ at positions 00 (for “0“), 01 (for “1“), 10 (for “2“).

you can reduce 6-color to 3-color, which is given in above link of your comment.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.