A Time-Optimal Randomized Parallel Algorithm for MIS
A Time-Optimal Randomized Parallel Algorithm for MIS
复制标题
DOI：
10.1137/1.9781611976465.172
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
M. Ghaffari;Bernhard Haeupler
中科院分区：
文献类型：
--
作者：
M. Ghaffari;Bernhard Haeupler
本文提出了一个随机并行算法，在互斥读互斥写（EREW）PRAM模型中，以高概率在O（logn）时间和O（mlog2n）工作量内计算最大独立集（MIS）.因此，MIS将RNC1。这种时间复杂度是最佳的，它改进了吕比[STOC'85]和阿龙，巴拜，和伊泰[JALG'86]，这仍然是最先进的在过去的35年的celebratedO（log2n）时间算法。
We present a randomized parallel algorithm, in the Exclusive-Read Exclusive-Write (EREW) PRAM model, that computes a Maximal Independent Set (MIS) inO(logn) time and usingO(mlog2n) work, with high probability. Thus, MIS ∊ RNC1. This time complexity is optimal and it improves on the celebratedO(log2n) 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.