On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph

Abstract: "We consider the parallel greedy algorithm of Coppersmith, Raghavan and Tompa [CRT] for finding the lexicographically first maximal independent set of a graph. We prove an [omega](log n) bound on the expected number if [sic] iterations for most edge densities. This complements the O(log n) bound proved in Calkin and Frieze [CF]."