A FAST PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM

被引：114

作者：

KARP, RM

WIGDERSON, A

机构：

[1] Univ of California at Berkeley,, Computer Science Div, Berkeley, CA,, USA, Univ of California at Berkeley, Computer Science Div, Berkeley, CA, USA

来源：

JOURNAL OF THE ACM | 1985年 / 32卷 / 04期

关键词：

COMPUTER SYSTEMS; DIGITAL - Parallel Processing;

D O I：

10.1145/4221.4226

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A parallel algorithm is presented that 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.

引用

页码：762 / 773

页数：12