Hopcroft–Karp algorithm

Hopcroft–Karp algorithm

Class	Graph algorithm
Data structure	Graph
Worst-case performance	${\displaystyle O(E{\sqrt {V}})}$
Worst-case space complexity	${\displaystyle O(V)}$

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching – a set of as many edges as possible with the property that no two edges share an endpoint. It runs in ${\displaystyle O(|E|{\sqrt {|V|}})}$ time in the worst case, where ${\displaystyle E}$ is set of edges in the graph, and ${\displaystyle V}$ is set of vertices of the graph. In the case of dense graphs the time bound becomes ${\displaystyle O(|V|^{2.5})}$, and for random graphs it runs in near-linear time.

...
Wikipedia