A Time-Optimal Randomized Parallel Algorithm for MIS
Mohsen Ghaffari, Bernhard Haeupler
2021Year
4Citations
2Top-tier citations
Abstract
We present a randomized parallel algorithm, in the Exclusive-Read Exclusive-Write (EREW) PRAM model, that computes a Maximal Independent Set (MIS) in O(log n) time and using O(m log2 n) work, with high probability. Thus, MIS ∊ RNC1. This time complexity is optimal and it improves on the celebrated O(log2 n) time algorithms of Luby [STOC'85] and Alon, Babai, and Itai [JALG'86], which had remained the state of the art for the past 35 years.
Ask about this paper
Ask your agent about it.
Lune has read the top-tier papers around this one, so every answer names the papers it rests on.
Your agent calls
Lunesearch_papers
Free to start. No credit card required.
Terminal
Install the CLIlune papers get 9b8247c9-cba8-4deb-841b-96871c0769c8Cited by top-tier papers2
- Local Computation of Maximal Independent SetMohsen GhaffariFOCS 2022 · 8 citations
- Sublinear Metric Steiner Forest via Maximal Independent SetSepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali VakilianSODA 2026
Related papers
- Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting SetMohsen Ghaffari, Christoph GrunauFOCS 2025 · 2 citations
- Distributed Maximal Matching and Maximal Independent Set on HypergraphsAlkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis OlivettiSODA 2023 · 8 citations
- Breaking Barriers for Distributed MIS by Faster Degree ReductionSeri Khoury, Aaron SchildSTOC 2026 · 3 citations
- Polylogarithmic-time deterministic network decomposition and distributed derandomizationVáclav Rozhon, Mohsen GhaffariSTOC 2020 · 15 citations
- O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent SetSepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani SundaresanSTOC 2024 · 2 citations
