A Fast Perfect-Matching Algorithm in Random Graphs
Olivier Goldschmidt, Dorit S. Hochbaum · SIAM Journal on Discrete Mathematics · 1990
The matching problem is to find a maximum collection of mutually nonadjacent edges in a graph. An algorithm is presented that delivers a perfect matching in a random graph almost surely. The expected running time of this algorithm is $O( n \log_e (1/p) + n)$, where n is the number of vertices in the graph and where p is the probability of an edge. This running time is faster than $O(n \log_e n)$, the expected running time of the best randomized algorithm of Angluin and Valiant.