b'@article{BMST05,'b'\nTITLE = {Matching Algorithms are Fast in Sparse Random Graphs},\nAUTHOR = {Bast, Holger and Mehlhorn, Kurt and Sch{\\"a}fer, Guido and Tamaki, Hisao},\nLANGUAGE = {eng},\nISSN = {1432-4350},\nLOCALID = {Local-ID: C1256428004B93B8-257B5C3871441CAAC1256FC0004404AB-BMST05},\nYEAR = {2006},\nDATE = {2006},\nABSTRACT = {We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on $n$ vertices, with high probability every non-maximum matching has an augmenting path of length $O(\\log n)$. This implies that augmenting path algorithms like the Hopcroft--Karp algorithm for bipartite graphs and the Micali--Vazirani algorithm for general graphs, which have a worst case running time of $O(m\\sqrt{n})$, run in time $O(m \\log n)$ with high probability, where $m$ is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least $\\ln (n)$ [\\emph{Average Case Analysis of Algorithms for Matchings and Related Problems}, Journal of the ACM, \\textbf{41}(6), 1994]. Our results hold, if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani.},\nJOURNAL = {Theory of Computing Systems},\nVOLUME = {39},\nPAGES = {3--14},\n}\n'