A Time-Optimal Randomized Parallel Algorithm for MIS
METADATA ONLY
Loading...
Author / Producer
Date
2021-01
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '21)
Journal / series
Volume
Pages / Article No.
2892 - 2903
Publisher
SIAM
Event
32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
08730 - Gruppe Häupler / Group Häupler
Notes
Funding
853109 - Distributed and Massively Parallel Graph Algorithms (EC)
184735 - Distributed Algorithms for Global Graph Problems (SNF)
184735 - Distributed Algorithms for Global Graph Problems (SNF)