Tight Analysis of Parallel Randomized Greedy MIS
Tight Analysis of Parallel Randomized Greedy MIS
复制标题
并行随机贪婪MIS的严格分析
DOI：
10.1145/3326165
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Noever
中科院分区：
文献类型：
--
作者：
Manuela Fischer;A. Noever
我们提供了一个严格的分析，该分析设置了经过良好的平行贪婪MIS算法的圆形复杂性，从而回答了Blelloch，Fineman和Shun的主要开放问题[SPAA'12]。算法的作品如下。感兴趣的主要问题是该算法是自1987年以来进行的，由Coppersmith，Raghavan和Tompa [focs'87]进行了研究。 n）在Calkin和Frieze [随机struc]和o（log2 n）的Erdős-rényi随机图中，其圆形的圆形圆形圆形的圆形和shun [spaa'12]的一般概率很高。我们证明了该算法的一般图中的o（log n）的高概率上限，并且该结合也很紧。 85，jalg'86]。
We provide a tight analysis that settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA’12]. The parallel/distributed randomized greedy Maximal Independent Set (MIS) algorithm works as follows. An order of the vertices is chosen uniformly at random. Then, in each round, all vertices that appear before their neighbors in the order are added to the independent set and removed from the graph along with their neighbors. The main question of interest is the number of rounds it takes until the graph is empty. This algorithm has been studied since 1987, initiated by Coppersmith, Raghavan, and Tompa [FOCS’87], and the previously best known bounds were O(log n) rounds in expectation for Erdős-Rényi random graphs by Calkin and Frieze [Random Struc. Alg.’90] and O(log2 n) rounds with high probability for general graphs by Blelloch, Fineman, and Shun [SPAA’12]. We prove a high probability upper bound of O(log n) on the round complexity of this algorithm in general graphs and that this bound is tight. This also shows that parallel randomized greedy MIS is as fast as the celebrated algorithm of Luby [STOC’85, JALG’86].