Premium
On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph
Author(s) -
Calkin Neil J.,
Frieze A. M.,
Kučera L.
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030210
Subject(s) - lexicographical order , mathematics , combinatorics , upper and lower bounds , graph , random graph , discrete mathematics , frieze , mathematical analysis , archaeology , history
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).