Hopcroft–Karp algorithm
In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in O ( | E | | V | ) {\displaystyle O(|E|{\sqrt {|V|}})} time in the worst case, where E {\displaystyle E} is set of edges in the graph, V {\displaystyle V} is set of vertices of the graph, and it is assumed that | E | = Ω ( | V | ) {\displaystyle |E|=\Omega (|V|)} .