Content deleted Content added
No edit summary |
Just added the basic definition and the basic idea behind the algorithm. Would add more tomorrow. |
||
Line 1:
== Introduction ==
The '''Hopcroft–Karp algorithm''' finds maximum cardinality [[matching]]s in [[bipartite graph]]s in <math>O(\sqrt{V} E)</math> time, where ''V'' is the number of vertices and ''E'' is the number of edges of the graph.<ref>John E. Hopcroft, Richard M. Karp: ''An <math>n^{5/2}</math> Algorithm for Maximum Matchings in Bipartite Graphs.'' SIAM J. Comput. 2(4), 225-231 (1973)</ref> <ref name=clrs>{{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]] | title = [[Introduction to Algorithms]] | origyear = 1990 | edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 696-697 | id = ISBN 0-262-03293-7}}</ref> In the worst case of dense graphs, i.e., when <math>E=O(V^2)</math>, the worst-case time estimate is <math>O(V^{5/2})</math>.
Line 4 ⟶ 8:
Instead of finding just a single augmenting path, the algorithm finds a maximal set of shortest paths in each iteration <ref>{{cite web|author=Norbert Blum|title=A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in Nonbipartite Graphs|url=http://citeseer.ist.psu.edu/258961.html|date=1999}}</ref>. As a result only <math>O(\sqrt{V})</math> iterations are needed.
== Definition ==
Consider a graph G(V,E). Consider these definitions relative to a matching M in G.
An alternating path would be a path in which the edges would belong alternatively to M and E-M.
A free vertex is a vertex which has no incoming edges which belong to M.
Finally, an augmenting path is an alternating path such that both its end points are free vertices.
== Algorithm ==
The Basic concept that the algorithm relies on is that if we have a matching N of size n, and P is the augmenting path relative to N, then the matching NΔP would have a size of n+1. Thus, since there would be no matching greater in size than the maximum matching, the maximum matching would not have an augmenting path.
== References ==
| |||