On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph
Neil J. Calkin, ALAN M. FRIEZE, Luděk Kučera · Random Structures and Algorithms · 1992
Abstract We consider the parallel greedy algorithm of Coppersmith, Raghavan, and Tompa (Proc. of 28th Annual IEEE Symp. on Foundations of Computer Science, pp. 260–269, 1987) for finding the lexicographically first maximal independent set of a graph. We prove an Ω(log n) bound on the expected number of iterations for most edge densities. This complements the O(log n) bound proved in Calkin and Frieze (Random Structures and Algorithms, Vol. 1, pp. 39–50, 1990).