Content deleted Content added
Citation bot (talk | contribs) m Alter: issue, title. Add: citeseerx, title-link. Removed URL that duplicated unique identifier. Formatted dashes. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | All pages linked from User:AManWithNoPlan/sandbox2. |
m reference needed |
||
Line 1:
{{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 as input a [[bipartite graph]] and produces as output a [[Maximum cardinality matching|maximum cardinality matching]] – 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 analysis|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 near-linear (in |E|) time{{reference needed}}.
The algorithm was found by {{harvs|first1=John|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard|last2=Karp|author2-link=Richard Karp|txt|year=1973}} and independently by {{harvs|first=Alexander|last=Karzanov|authorlink=Alexander V. Karzanov|year=1973|txt}}.{{sfnp|Dinitz|2006}} As in previous methods for matching such as the [[Hungarian algorithm]] and the work of {{harvtxt|Edmonds|1965}}, the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths: sequences of edges that alternate between being in and out of the matching, such that swapping which edges of the path are in and which are out of the matching produces a larger matching. However, instead of finding just a single augmenting path per iteration, the algorithm finds a maximal set of shortest augmenting paths. As a result, only <math>O(\sqrt{|V|})</math> iterations are needed. The same principle has also been used to develop more complicated algorithms for non-bipartite matching with the same asymptotic running time as the Hopcroft–Karp algorithm.
| |||