Hopcroft–Karp algorithm

Summary

The Hopcroft–Karp algorithm finds a maximum matching in a bipartite graph. Like simpler methods, it enlarges the matching along augmenting paths, but in each phase it uses many shortest augmenting paths at once. Only $O(\sqrt{n})$ phases are needed, which gives the running time $O(m \sqrt{n})$ on $n$ vertices and $m$ edges.