Engineering Papers⌕ Search

DOE OSTI · 1434878

Distributed-Memory Fast Maximal Independent Set

Abstract

The Maximal Independent Set (MIS) graph problem arises in many applications such as computer vision, information theory, molecular biology, and process scheduling. The growing scale of MIS problems suggests the use of distributed-memory hardware as a cost-effective approach to providing necessary compute and memory resources. Luby proposed four randomized algorithms to solve the MIS problem. All those algorithms are designed focusing on shared-memory machines and are analyzed using the PRAM model. These algorithms do not have direct efficient distributed-memory implementations. In this paper, we extend two of Luby’s seminal MIS algorithms, “Luby(A)” and “Luby(B),” to distributed-memory execution, and we evaluate their performance. We compare our results with the “Filtered MIS” implementation in the Combinatorial BLAS library for two types of synthetic graph inputs.

Explore related subjects

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Zalewski, Marcin J., Lumsdaine, Andrew. 2017-09-13. Distributed-Memory Fast Maximal Independent Set. https://doi.org/10.1109/hpec.2017.8091032. https://engineeringpapers.com/record/osti%3A1434878/distributed-memory-fast-maximal-independent-set

Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Engineering Papers by Indiciae: BibTeX · RIS.