ALCOMFT-TR-03-111
|
![ALCOM-FT](../Main/logo_160x41.gif)
|
Holger Bast, Kurt Mehlhorn, Guido Schäfer and Hisao Tamaki
Matching Algorithms are Fast in Sparse Random Graphs
MPI.
Work package 4.
November 2003.
Abstract: 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) [Average Case Analysis of Algorithms for Matchings and Related Problems, Journal of the
ACM, 41(6), 1994]. Our result holds, if only the average degree is a large enough constant.
At the same time we simplify the analysis of Motwani.
Postscript file: ALCOMFT-TR-03-111.ps.gz (95 kb).
System maintainer Gerth Stølting Brodal <gerth@cs.au.dk>