Hopcroft–Karp algorithm

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

Algorithm

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

Output: Matching ${\displaystyle M\subseteq E}$ 

${\displaystyle M\leftarrow \emptyset }$ 

repeat

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

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

until ${\displaystyle {\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)