Hopcroft–Karp algorithm: Difference between revisions

Revision as of 14:54, 5 April 2022

Revision as of 21:20, 16 May 2022

Line 1:

{{Short description|Algorithm for maximum cardinality matching}}

{{Infobox algorithm|image = |data = [[Graph (data structure)|Graph]]|time = <math>O(E \sqrt V)</math>|class = Graph algorithm|space = <math>O(V)</math>}}In [[computer science]], the '''Hopcroft–Karp algorithm''' (sometimes more accurately called the '''Hopcroft–Karp–Karzanov algorithm''')<ref>{{harvtxt|Gabow|2017}}; {{harvtxt|Annamalai|2018}}</ref> 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 <math>O(|E|\sqrt{|V|})</math> time in the [[worst case]], where <math>E</math> is set of edges in the graph, <math>V</math> is set of vertices of the graph, and it is assumed that <math>|E|=\Omega(|V|)</math>. In the case of [[dense graph]]s the time bound becomes <math>O(|V|^{2.5})</math>, and for sparse [[random graph]]s it runs in time <math>O(|E|\log |V|)</math> with high probability.{{sfnp|Bast|Mehlhorn|Schäfer|Tamaki|2006}}