ausblenden:
Schlagwörter:
-
Zusammenfassung:
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 nonmaximum
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(mpn), run in time O(mlog 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
results hold, if only the average degree is a large enough constant. At the
same time we simplify the analysis of Motwani.