Hopcroft–Karp algorithm: Difference between revisions

Revision as of 10:39, 3 September 2007

Revision as of 10:39, 3 September 2007

Line 1:

The '''Hopcroft–Karp algorithm''' finds maximum cardinality [[matching]]s in [[bipartite graph]]s in <math>O(\sqrt{V} E)</math> time. It 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 [[minimal vertex cover|König's theorem (graph theory)|minimal vertex cover]] associated with the matching.

== Algorithm ==