Graph Coloring on a Coarse Grained Multiprocessor
Assefaw Hadish Gebremedhin, Isabelle Guérin Lassous, Jens Gustedt, Jan Arne Telle · 2000
. We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph G with a guarantee of at most D G +1 colors. 1 Introduction and Overview The problem of graph coloring is crucial both for the applications of graph algorithms to real world problems and for the domain of parallel graph algorithms itself. For the latter, graph colorings using a bounded number of colors are often used in a theoretical setting to ensure the independence of tasks that are to be accomplished on the vertices of a graph: knowing that the color classes form independent sets that don't interact each one of them can be treated in parallel. For a long time, no efficient parallel implementation of a graph coloring heuristic with good speedups was known, see Allwright et al. (1995). However, in a recent result, Gebremedhin and Manne (1999a, 1999b) present an algorithm and an implementation for a shared memory computer that proves to be theoretically and practically efficient with ...