Maximum matchings in sparse random graphs: Karp–Sipser revisited
✍ Scribed by Jonathan Aronson; Alan Frieze; Boris G. Pittel
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 490 KB
- Volume
- 12
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on
x Foundations of Computing, 1981, pp. 364᎐375 . We give significantly improved estimates of the errors made by the algorithm. For the subcritical case where ce 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 1r5qoŽ1. of maximum size.