Title

Parallel Coloring Of Graphs - 2 Approximate Algorithms

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Int. J. Comput. Math.

Keywords

Mathematics; Applied; Parallel Algorithms; Graph Coloring; Supercomputing

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

Journal Title

International Journal of Computer Mathematics

Volume

27

Issue/Number

3-4

Publication Date

1-1-1989

Document Type

Article

Language

English

First Page

147

Last Page

158

WOS Identifier

WOS:A1989U297800003

ISSN

0020-7160

Share

COinS