The Average Performance of the Greedy Matching Algorithm

Authors
Dyer, Martin Frieze, Alan Pittel, Boris
Citation
Dyer, Martin et al., The Average Performance of the Greedy Matching Algorithm, Annals of applied probability , 3(2), 1993, pp. 526-552
Journal title
Annals of applied probability → ACNP
ISSN journal
10505164
Volume
3
Issue
2
Year of publication
1993
Pages
526 - 552
Database
ACNP
SICI code
Abstract
We consider the expected performance of two greedy matching algorithms on sparse random graphs and also on random trees. In all cases we establish expressions for the mean and variance of the number of edges chosen and establish asymptotic normality.