Probabilistic analysis of a parallel algorithm for finding maximal independent sets
Neil J. Calkin, ALAN M. FRIEZE · Random Structures and Algorithms · 1990
Abstract We consider a natural parallel version of the classical greedy algorithm for finding a maximal independent set in a graph. This version was studied in Coppersmith, Raghavan, and Tompa and they conjecture there that its expected running time on random graphs of arbitrary edge density of O (log n). We prove that conjecture.