Graph Coloring on a Coarse Grained Multiprocessor (extended abstract)

Assefaw Hadish Hadish Gebremedhin , Isabelle Guérin Lassous , Jens Gustedt (1) , Jan Arne Telle

1 RESEDAS - Software Tools for Telecommunications and Distributed Systems

We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph $G$ with a guarantee of at most $\D +1$ colors.

Mots clés: graph coloring; parallelism; CGM

Domaines: Autre [cs.OH]

Assefaw Hadish Hadish Gebremedhin, Isabelle Guérin Lassous, Jens Gustedt, Jan Arne Telle. Graph Coloring on a Coarse Grained Multiprocessor (extended abstract). [Research Report] RR-3906, INRIA. 2000, pp.11. ⟨inria-00072747⟩