|
The '''Hopcroft–Karp algorithm''' finds maximum cardinality [[matching]]s in [[bipartite graph]]s in <math>O(\sqrt{V} E)</math> time, (another estimation iswhere ''O(V <sup>5/2</sup>)'' <ref>Lipskiis W.,the number Kombinatorykaof dlavertices Programistow,and [Combinatorics''E'' foris Programmers],the number Wydawnictwaof Naukowo-Techniczne,edges Warzawa,of 1982the graph.</ref name=clrs>).{{cite Itbook is| anauthor adaptation= of[[Thomas theH. Cormen]], [[Edmonds-KarpCharles algorithmE. Leiserson]], for[[Ronald maximumL. flowRivest]], sinceand bipartite[[Clifford matchingStein]] is| equivalenttitle = [[Introduction to findingAlgorithms]] the| maximumorigyear (integer)= flow1990 if| theedition vertices= in2nd eachedition partition| areyear considered= sources2001 (respectively| sinks)publisher of= capacityMIT 1.Press Theand [[MaxMcGraw-flowHill min| pages = 696-cut697 theorem|minimal cut]]id associated= withISBN 0-262-03293-7}}</ref> In the flowworst iscase equivalentof todense thegraphs, [[König'si.e., theoremwhen <math>E=O(graph theoryV^2)|minimal</math>, vertexthe cover]]worst-case associatedtime withestimate theis matching<math>O(V^{5/2})</math>.
The algorithm is an adaptation of the [[Edmonds-Karp algorithm]] for maximum flow, since bipartite matching is equivalent to finding the maximum (integer) flow if the vertices in each partition are considered sources (respectively sinks) of capacity 1. The [[Max-flow min-cut theorem|minimal cut]] associated with the flow is equivalent to the [[König's theorem (graph theory)|minimal vertex cover]] associated with the matching.
== Algorithm ==
: '''Input''': Bipartite graph <math>G(V=L \cup R, E)</math>
: '''Output''': Matching <math>M \subseteq E</math>
: <math>M \leftarrow \empty</math>
: '''repeat'''
:: <math>\mathcal P \leftarrow \{P_1, P_2, \dots, P_k\}</math> ''maximal set of vertex-disjoint shortest augmenting paths''
:: <math>M \leftarrow M \oplus (P_1 \cup P_2 \cup \dots \cup P_k)</math>
: '''until''' <math>\mathcal P = \empty</math>
== References ==
* {{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]] | title = [[Introduction to Algorithms]] | origyear = 1990 | edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 696-697 | chapter = 26 | id = ISBN 0-262-03293-7}}
* Even S., Kariv O., ''An O(n<sup>5/2</sup>) algorithm for maximum matching in general graphs'', Proc. 16th Annual Symp. of Foundations of Computer Sci., IEEE, 1975, p. 100-112.
{{comp-sci-stub}}
| 