A Time-Optimal Randomized Parallel Algorithm for MIS

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 log 2 n ) work, with high probability. Thus, MIS ∊ RNC 1. This time complexity is optimal and it improves on the celebrated O (log 2 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.

Authors

• Mohsen Ghaffari 0001
• Bernhard Haeupler

Keywords

No keywords are indexed for this paper.