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 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?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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$.

share|improve this answer
    
thank you, for explanation, the last point is why in case of parent and child on the second iteration, when $c_p = 01010$ and $c_c= 10001$, 5 digits, differ in 1th bit, so $c_c = 001+0=10$, but it's $001$ –  fog Dec 17 '12 at 12:13
    
Yes, I'm pretty sure it should be $000 || 1$ (concatenation) giving $0001$. Unless there is some way to show that after the first iteration, the difference can never be in the most significant bit, in which case you only need to represent indices from 0-3 using 2 bits. But since such a proof is not provided, and since it is safe to assume that the first differing position can also be in the MSB, I would say the safer way (and giving correct results) will be to take 3 bits for the differing index, and the result would be $0001$. –  Paresh Dec 17 '12 at 13:15

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.