Exploiting parallelism for undirected graph coloring

Parallel graph coloring algorithms are based on the observation that if we split the graph into multiple independent sets of vertices, we can color those in parallel without introducing any conflict.

An independent set is defined as the collection or set of vertices where no two vertices share an edge.

To develop a parallelized version of the sequential greedy graph coloring algorithm from the previous section, we will be relying on a simple, yet effective algorithm proposed by Jones and Plassmann [6]. Before diving into the implementation details, let's take a few minutes to explain how the algorithm generates independent sets and how can we guarantee that our compute function will avoid ...

Get Hands-On Software Engineering with Golang now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.