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

1986/12/01 by Noga Alon, László Babai, Alon Itai · 541 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Deterministic algorithm #Discrete mathematics #Graph #Independent set #Limits and Structures in Graph Theory #Line graph #Mathematics #Maximal independent set #Pairwise comparison #Parallel algorithm #Pathwidth #Probabilistic analysis of algorithms #Probabilistic logic #Randomized algorithm #SIMPLE algorithm #Set (abstract data type) #Simple (philosophy)

paper · doi:10.1016/0196-6774(86)90019-2

published in Journal of Algorithms 7(4), 567-583 (Elsevier BV)

crossref issued 1986/12/01 · crossref published 1986/12/01 · crossref published-print 1986/12/01 · openalex publication_date 1986/12/01 · crossref created 2005/02/10 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · crossref indexed 2026/08/01 · openalex updated_date 2026/08/01

Citations

• An overview of computational complexity
• Some remarks on the theory of graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem

Cited by

• The Algorithmic Aspects of the Regularity Lemma
• Small-bias probability spaces: efficient constructions and applications
• Linear Probing with Constant Independence
• ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS
• Adaptive Exact Learning of Decision Trees from Membership Queries
• The Space Complexity of Approximating the Frequency Moments
• The space complexity of approximating the frequency moments
• Local Computation: Lower and Upper Bounds
• Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
• Primal-Dual Distance Bounds of Linear Codes With Application to Cryptography
• Round Compression for Parallel Graph Algorithms in Strongly Sublinear\n Space
• Approximating the Cut-Norm via Grothendieck's Inequality
• Simple Constructions of Almost k‐wise Independent Random Variables
• Self-Stabilizing Algorithms in the Uniform Port Model
• Maximal independent set [wikipedia]
• Small-bias sample space [wikipedia]