Hopcroft–Karp algorithm: Difference between revisions

Revision as of 16:45, 29 April 2008

Revision as of 13:22, 18 June 2008

Line 1:

== Introduction ==

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 | edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 696-697 | id = ISBN 0-262-03293-7}}</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>.

Line 14 ⟶ 11:

Consider a graph G(V,E). The following definitions are relative to a matching M in G.

-* An alternating path is a path in which the edges would belong alternatively to M and E-M.

-* A free vertex is a vertex which has no incoming edges which belong to M.

-* Finally, an augmenting path is an alternating path such that both its end points are free vertices.

== Algorithm ==

Line 96 ⟶ 93:

[[Category:Graph algorithms]]

[[Category:Articles with example pseudocode]]

[[de:Algorithmus von Hopcroft und Karp]]