Hopcroft–Karp algorithm

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

Algorithm

Input: Bipartite graph $G(V=L\cup R,E)$

Output: Matching $M\subseteq E$

$M\leftarrow \emptyset$

repeat

${\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}$ maximum set of vertex-disjoint shortest augmenting paths

$M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})$

until ${\mathcal {P}}=\emptyset$

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "26". Introduction to Algorithms (2nd edition ed.). MIT Press and McGraw-Hill. pp. 696–697. ISBN 0262032937. {{cite book}}: |edition= has extra text (help)CS1 maint: multiple names: authors list (link)