Parallel Coloring Of Graphs - 2 Approximate Algorithms
Abbreviated Journal Title
Int. J. Comput. Math.
Mathematics; Applied; Parallel Algorithms; Graph Coloring; Supercomputing
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
International Journal of Computer Mathematics
Das, Sajal K. and Deo, Narsingh, "Parallel Coloring Of Graphs - 2 Approximate Algorithms" (1989). Faculty Bibliography 1980s. 764.