A Parallel Maximal Independent Set Algorithm

Mark Adams

Department of Civil Engineering
University of California at Berkeley
Berkeley, CA 94720


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 (FE) models. For appropriately partitioned bounded degree graphs, it is shown that the running time of our algorithm under the P-RAM computational model is of O(1), which is an improvement over the previous best P-RAM complexity for this class of graphs. We present numerical experiments on an IBM SP, that confirm our P-RAM complexity model is indicative of the performance one can expect with practical partitions on graphs from FE problems.