Content deleted Content added
SFN all sources to eliminate duplicate cite. |
|||
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]] – 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}}
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.
The Hopcroft–Karp algorithm can be seen as a special case of [[Dinic's algorithm]] for the [[maximum flow problem]].
==Augmenting paths==
Line 128:
==References==
{{refbegin}}
*{{citation|first1=Ravindra K.|last1=Ahuja|author1-link=Ravindra K. Ahuja|first2=Thomas L.|last2=Magnanti|author2-link=Thomas L. Magnanti|first3=James B.|last3=Orlin|author3-link=James B. Orlin|title=Network Flows: Theory, Algorithms and Applications|publisher=Prentice-Hall|year=1993}}.
*{{citation|first1=H.|last1=Alt|first2=N.|last2=Blum|first3=K.|last3=Mehlhorn|author3-link=Kurt Mehlhorn|first4=M.|last4=Paul|title=Computing a maximum cardinality matching in a bipartite graph in time <math>\scriptstyle O\left(n^{1.5}\sqrt{\frac{m}{\log n}}\right)</math>|journal=Information Processing Letters|volume=37|issue=4|pages=237–240|year=1991|doi=10.1016/0020-0190(91)90195-N}}.
Line 145 ⟶ 146:
| year = 2006}}
*{{citation|first1=S. Frank|last1=Chang|first2=S. Thomas|last2=McCormick|title=A faster implementation of a bipartite cardinality matching algorithm|publisher=Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia|year=1990}}. As cited by {{harvtxt|Setubal|1996}}.
*{{citation|first=Kenneth|last=Darby-Dowman|title=The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms|publisher=Ph.D. thesis, Brunel University |year=1980}}. As cited by {{harvtxt|Setubal|1996}}.
*{{citation|last=Dinitz|first=Yefim|editor1-last=Goldreich|editor1-first=Oded|editor1-link=Oded Goldreich |editor2-last=Rosenberg|editor2-first=Arnold L.|editor2-link=Arnold L. Rosenberg|editor3-last=Selman |editor3-first=Alan L. |editor3-link=Alan Selman|contribution=Dinitz' Algorithm: The Original Version and Even's Version|doi=10.1007/11685654_10|___location=Berlin and Heidelberg|pages=218–240|publisher=Springer |series=Lecture Notes in Computer Science |title=Theoretical Computer Science: Essays in Memory of Shimon Even|volume=3895|year=2006}}.
*{{citation |
*{{citation|last=Gabow|first=Harold N.|author-link=Harold N. Gabow|doi=10.3233/FI-2017-1555|issue=1–4|journal=Fundamenta Informaticae|mr=3690573|pages=109–130|title=The weighted matching approach to maximum cardinality matching|volume=154|year=2017|arxiv=1703.03998|s2cid=386509}}
*{{citation|first1=Harold N.|last1=Gabow|author1-link=Harold N. Gabow|first2=Robert E.|last2=Tarjan|author2-link=Robert Tarjan|title=Faster scaling algorithms for general graph matching problems|journal=Journal of the ACM|volume=38|issue=4|year=1991|pages=815–853|doi=10.1145/115234.115366|s2cid=18350108}}.
*{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}. Previously announced at the 12th Annual Symposium on Switching and Automata Theory, 1971.
*{{citation|first=A. V.|last=Karzanov|authorlink=Alexander V. Karzanov|title=An exact estimate of an algorithm for finding a maximum flow, applied to the problem on representatives|journal=Problems in Cybernetics |volume=5 |pages=66–70|year=1973}}. Previously announced at the Seminar on Combinatorial Mathematics (Moscow, 1971).
*{{citation |
*{{citation |
*{{citation|first=Rajeev|last=Motwani|authorlink=Rajeev Motwani|title=Average-case analysis of algorithms for matchings and related problems|year=1994|journal=Journal of the ACM|volume=41|issue=6|pages=1329–1356|doi=10.1145/195613.195663|s2cid=2968208}}.
*{{citation|last=Setubal|first=João C.|contribution=New experimental results for bipartite matching |title=Proc. Netflow93|publisher=Dept. of Informatics, Univ. of Pisa|pages=211–216|year=1993}}. As cited by {{harvtxt|Setubal|1996}}.
*{{citation|last=Setubal|first=João C.|title=Sequential and parallel experimental results with bipartite matching algorithms|publisher=Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas|year=1996 |citeseerx=10.1.1.48.3539}}.
*{{Cite book|last=Tarjan|first=Robert Endre|title=Data Structures and Network Algorithms|year=1983 |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}}
*{{citation|last=Vazirani|first=Vijay|title=An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm|publisher= CoRR abs/1210.4594|year=2012|arxiv=1210.4594|bibcode=2012arXiv1210.4594V}}.
{{refend}}
{{DEFAULTSORT:Hopcroft-Karp algorithm}}
| |||