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

Calkin Neil J. | Zendy; Frieze A. M. | Zendy; Kučera L. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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).

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research