Hopcroft-Karp algorithm

From Wikipedia, the free encyclopedia

The Hopcroft-Karp algorithm finds maximum cardinality matchings in bipartite graphs in O(\sqrt{V} E) time.

[edit] Algorithm

Input: Bipartite graph G(V=L \cup R, E)
Output: Matching M \subseteq E
M \leftarrow \empty
repeat
\mathcal P \leftarrow \{P_1, P_2, \dots, P_k\} maximal set of vertex-disjoint shortest augmenting paths
M \leftarrow M \oplus (P_1 \cup P_2 \cup \dots \cup P_k)
until \mathcal P = \empty

[edit] References

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../h/o/p/Hopcroft-Karp_algorithm_6a90.html"
In other languages