Hopcroft–Karp algorithm: Difference between revisions

Revision as of 13:22, 18 June 2008

Revision as of 18:46, 18 June 2008

Line 1:

The '''Hopcroft–Karp algorithm''' finds maximum cardinality [[matching]]s in [[bipartite graph]]s in <math>O(\sqrt{V} E)</math> time, where ''V'' is the number of vertices and ''E'' is the number of edges of the graph.<ref>John E. Hopcroft, Richard M. Karp: ''An <math>n^{5/2}</math> Algorithm for Maximum Matchings in Bipartite Graphs.'' SIAM J. Comput. 2(4), 225-231 (1973)</ref> <ref name=clrs>{{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]] | title = [[Introduction to Algorithms]] | origyear = 1990 2| edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages =pp. 696-697 | id = ISBN 0-262-03293-7696–697}}</ref> In the worst case of dense graphs, i.e., when <math>E=O(V^2)</math>, the worst-case time estimate is <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.