Content deleted Content added
mention connection to Dinic |
add citation |
||
Line 3:
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''. These paths are sequences of edges of the graph, which alternate between edges in the matching and edges out of the partial matching, and where the initial and final edge are not in the partial matching. Finding an augmenting path allows us to increment the size of the partial matching, by simply toggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa). Simpler algorithms for bipartite matching, such as the [[Ford–Fulkerson algorithm]]‚ find one augmenting path per iteration: the Hopkroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only <math>O(\sqrt{|V|})</math> iterations are needed instead of <math>O(V)</math> iterations. The same performance of <math>O(|E|\sqrt{|V|})</math> can be achieved to find maximum cardinality matchings in arbitrary graphs, with the more complicated algorithm of Micali and Vazirani<ref>{{Cite journal|last=Peterson|first=Paul A.|last2=Loui|first2=Michael C.|date=1988-11-01|title=The general maximum matching algorithm of micali and vazirani|url=https://doi.org/10.1007/BF01762129|journal=Algorithmica|language=en|volume=3|issue=1|pages=511–533|doi=10.1007/BF01762129|issn=1432-0541}}</ref>.
The Hopcroft–Karp algorithm can be seen as a special case of [[Dinic's algorithm]] for the [[maximum flow problem]].<ref>{{Cite book|last=Tarjan|first=Robert Endre|url=https://epubs.siam.org/doi/book/10.1137/1.9781611970265|title=Data Structures and Network Algorithms|date=1983-01-01|publisher=Society for Industrial and Applied Mathematics|isbn=978-0-89871-187-5|series=CBMS-NSF Regional Conference Series in Applied Mathematics|doi=10.1137/1.9781611970265}}, p102</ref>
==Augmenting paths==
| |||