A fast parallel algorithm for the maximal independent set problem
A fast parallel algorithm for the maximal independent set problem
复制标题
DOI：
10.1145/800057.808690
复制
发表时间：
1984-12
期刊：
影响因子：
--
通讯作者：
R. Karp;A. Wigderson
中科院分区：
文献类型：
--
作者：
R. Karp;A. Wigderson
提出了一种并行算法，该算法接受为输入图G，并在G中产生最大独立的顶点。并使用o（（n/log n）3）处理器，其中n是G中的顶点。该算法具有几种可能找到其他应用程序的新型功能。通过确定性抽样以及使用常规鸽子孔原理的“动态鸽子原理”。
A parallel algorithm is presented which accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O((log n)4) time and uses O((n/log n)3) processors, where n is the number of vertices in G. The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle.