Premium
Probabilistic analysis of a parallel algorithm for finding maximal independent sets
Author(s) -
Calkin Neil,
Frieze Alan
Publication year - 1990
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.3240010104
Subject(s) - conjecture , mathematics , combinatorics , probabilistic logic , running time , discrete mathematics , probabilistic analysis of algorithms , set (abstract data type) , graph , random graph , algorithm , computer science , statistics , programming language
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom