Premium
Maximum matchings in sparse random graphs: Karp–Sipser revisited
Author(s) -
Aronson Jonathan,
Frieze Alan,
Pittel Boris G.
Publication year - 1998
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/(sici)1098-2418(199803)12:2<111::aid-rsa1>3.0.co;2-#
Subject(s) - combinatorics , mathematics , random graph , computer science , matching (statistics) , discrete mathematics , statistics , graph
We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G n , c / n , where c >0 is constant. The algorithm was first proposed by Karp and Sipser [ Proceedings of the Twenty‐Second Annual IEEE Symposium on Foundations of Computing , 1981, pp. 364–375]. We give significantly improved estimates of the errors made by the algorithm. For the subcritical case where c < e we show that the algorithm finds a maximum matching with high probability. If c > e then with high probability the algorithm produces a matching which is within n 1/5+ o (1) of maximum size. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 111–177, 1998