Mark Adams

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-98-993
January 1998

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/CSD-98-993.pdf

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.

BibTeX citation:

@techreport{Adams:CSD-98-993,
    Author = {Adams, Mark},
    Title = {A Parallel Maximal Independent Set Algorithm},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1998},
    Month = {Jan},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/5560.html},
    Number = {UCB/CSD-98-993},
    Abstract = {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 <i>O</i>(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.}
}

EndNote citation:

%0 Report
%A Adams, Mark
%T A Parallel Maximal Independent Set Algorithm
%I EECS Department, University of California, Berkeley
%D 1998
%@ UCB/CSD-98-993
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/5560.html
%F Adams:CSD-98-993