A Parallel Maximal Independent Set Algorithm
Mark F. Adams, James Weldon Demmel · 1998
The parallel construction of maximal independent sets is a useful building block for many algorithms in the computational sciences, including graph coloring and multigrid coarse grid creation on unstructured meshes. We present an efficient asynchronous maximal independent set algorithm for use on parallel computers, for "well partitioned" graphs, that arise from finite element models. For appropriately partitioned bounded degree graphs, it is shown that the running time of our algorithm under the PRAM computational model is O(1), which is an improvement over the previous best PRAM complexity for this class of graphs. We present numerical experiments on an IBM SP, that confirm our PRAM complexity model is indicative of the performance one can expect with practical partitions on graphs from finite element problems. Key words: maximal independent sets, multigrid, parallel algorithms, graph coloring AMS(MOS) subject classification: 65F10, 65F50, 65Y05, 68Q22, 68R10, 05C85 1 Intr...