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.

There is an exercise in Distributed Algorithm I have some difficulties to solve. There are few ideas, however nothing useful at the time. I will appreciate any help with it.

Graph $G$ is a $k$-tree if it's possible to divide all it's edges to $k$ trees ($k$ subgraphs without a loop). Given network $N$ every processor knows it's parent and it's children in every tree. Using algorithm for 3-coloring of an arbitrary tree (as describe in Vertex Coloring) show that the given graph $G$ is $3k$-colorable in the same time complexity $O(\log^*n)$.

Ideas: every vertex $v$ could belong to one or more trees among $k$ trees. For every particular tree vertex $v$ belongs to, vertex $v$ knows it's parent in this tree and it's children in this tree. Exercise asks to color a graph $G$ in $3k$ colors. Running the mentioned algorithm for any particular tree we will get correct 3-colorable $k$ trees, each vertex will have $m$ different color labels, where $m$ is number of trees, vertex $v$ belongs to.

Now the difficult part, concatenation of all $m$ color labels in one color for vertex $v$ will result in $3^k$ different colors for graph $G$.

In general, simplification of the problem is on the picture.

enter image description here

Vertices $v$ and $u$ are connected by an edge (on the picture the edge belongs to the 1 tree, in principle it doesn't matter, we could draw a parallel edge that belongs to 2 tree), $v$ and $u$ belong to 1 tree and 2 tree. After running 3-colorability algorithm for every tree we will get the correct colorability, now the problem is to make color assignments to vertices $v$ and $u$ as vertices of the graph $G$ based on the color assignment of these vertices for 1 tree and 2 tree, and of course because $u$ and $v$ are connected by an edge in graph $G$, the colors should be different.

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.