A fast parallel algorithm for the maximal independent set problem

ABSTRACT

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.

REFERENCES

• 1: Stephen A. Cook, An overview of computational complexity, Communications of the ACM, v.26 n.6, p.400-408, June 1983 [doi>10.1145/358141.358144]
• 2: Cook, S. A., "The Classification of Problems which have Fast Parallel Algorithms," Technical Report No. 164/83, Department of Computer Science, University of Toronto (1983).
• 3: Hall, M., Combinatorial Theory, Blaisdell (1967).
• 4: Jones, N. D., Lien, Y. E., Laaser, W. T., "New Problems Complete for Nondeterministic Log Space," Mathematical Systems Theory 10, 1-17 (1976).
• 5: Lev, G., "Size Bounds and Parallel Algorithms for Networks," Report CST-8-80, Dept. of Computer Science, University of Edinburgh (1980).
• 6: Valiant, L. G., "Parallel Computation," Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science, (1982).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Algorithms, Theory