Chapter 7

In the previous week we have seen some algorithms for basic graph problems such as connected components, minimum spanning trees, and shortest paths. In this week, we study more graph algorithms that require some additional techniques. 7.1 Graph Coloring Vertex coloring of graphs is a problem of huge interest given its applications to various problems such as scheudling and routing. In the sequential setting a famous and simple algorithm is the greedy algorithm that assigns the smallest available color in the neighborhood to each vertex. This can be seen to use at most ∆ + 1 colors where ∆ is the maximum degree of the graph. Further progess is often highly complicated given the inherent difficulty of solving this problem even approximately close. The same difficulty applies to the parallel setting also. Hence, most researchers have tried to arrive at a coloring that uses only O(∆) colors and can run in a poly-logarithmic time. In this section, we study two approaches to the problem. Interestingly, both the approaches use randomization and it has been shown that no determinisitc algorithm can exist in the parallel setting that uses only O(∆) colors. 7.1.1 Algorithm – I: Luby’s algorithm The first algorithm that we study has its origins in a paper of Luby [3]. The idea is to let vertices choos