A fast and simple randomized parallel algorithm for the maximal independent set problem

Noga Alon, László Babai, Alon Itai

Research output: Contribution to journalArticle

456 Scopus citations

Abstract

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|dmax) processors is O(log n), where dmax denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log2n). Previously, an O(log4n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log2n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.

Original languageEnglish (US)
Pages (from-to)567-583
Number of pages17
JournalJournal of Algorithms
Volume7
Issue number4
DOIs
StatePublished - Dec 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A fast and simple randomized parallel algorithm for the maximal independent set problem'. Together they form a unique fingerprint.

  • Cite this