Parallel coloring of graphs: two approximate algorithms

Abstract

Graph coloring is an abstraction of scheduling problems. Using an exclusive-read and exclusive-write (EREW) parallel random access machine (PRAM) model, two approximate coloring algorithms are parallelized. The performance analysis reveals that the parallel largest-degree-first algorithm is efficient for regular or near-regular graphs; while the second, a costlier but more easily parallelizable algorithm, yields optimal speedup for graphs of widely varying densities.

Keywords:

• Parallel algorithms
• graph coloring
• supercomputing

C.R. Categories:

• G.2.2
• C.1.2