[Solved]: Distributed 6-color Vertex Coloring

Problem Detail: 

I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10).

Here is a short description

Idea of the algorithm: We start with color labels that have $\log n$ bits. In each synchronous round we compute a new label with exponentially smaller size than the previous label, still guaranteed to have a valid vertex coloring.

Let $i$ be the smallest index where $c_v$ and $c_p$ differ; the new label is $i$ (as a bitstring) followed by the bit $c_v(i)$ itself

Grand-parent 0010110000 -> 10010 -> … Parent       1010010000 -> 01010 -> 111 Child        0110010000 -> 10001 -> 001 

The problem I cannot understand this example. Let's take Grand-parent($c_p$ = 0010110000) and parent($c_v$ = 1010010000), on the round when $c_v$ receives $c_p$, so we need to change $c_v$. They differ in 5th bit, counting from 0 (5 in binary is 101), so according to definition, $c_p$ is "$101$"+$c_p[5]=1010$, but in example it's 01010, what I get wrong?

Asked By : com

Answered By : Paresh

The labels $c_v$ and $c_p$ are relative. So when a node (parent in your example) having $c_v = 1010010000$ receives from its parent (grandparent in your example) an id $c_p = 0010110000$, the difference, as you correctly point out, is in the fifth position.

Now, the total number of bits in the original ids is 10, so representing any index (0-9) will require 4 bits. So, the new id will have 4 bits from the position difference + 1 bit for the differing bit. Now, $$(5)_{10} = (0101)_2$$

Note, we use 4 bits as discussed above, so that all new ids, can have the same number of bits. Then, $c_v(5) = 0$ is concatenated towards the LSB side, giving the new id: $01010$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7459