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
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.