Hopcroft–Karp algorithm: Difference between revisions

Revision as of 12:36, 19 November 2007

Revision as of 12:29, 14 April 2008

Line 3:

The algorithm is an adaptation of the [[Edmonds-Karp algorithm]] for maximum flow, since bipartite matching is equivalent to finding the maximum (integer) flow if the vertices in each partition are considered sources (respectively sinks) of capacity 1. The [[Max-flow min-cut theorem|minimal cut]] associated with the flow is equivalent to the [[König's theorem (graph theory)|minimal vertex cover]] associated with the matching.

Instead of finding just a single augmenting path, the algorithm finds a maximal set of shortestestshortest 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.

== References ==