Greed is Good: Optimistic Algorithms for Bipartite-Graph Partial Coloring on Multicore Architectures

Mustafa Kemal Taş, Kamer Kaya, Erik Saule

In parallel computing, a valid graph coloring yields a lock-free processing of the colored tasks, data points, etc., without expensive synchronization mechanisms. However, coloring…