Hopcroft–Karp algorithm: Difference between revisions

Revision as of 16:44, 10 November 2007

Revision as of 16:49, 10 November 2007

Line 1:

The '''Hopcroft–Karp algorithm''' finds maximum cardinality [[matching]]s in [[bipartite graph]]s in <math>O(\sqrt{V} E)</math> time (another estimation is O(V ^5/2) <ref> Lipski W., Kombinatoryka dla Programistow, [Combinatorics for Programmers], Wydawnictwa Naukowo-Techniczne, Warzawa, 1982.</ref>). It 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 ==

Line 14:

* {{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}}

<references />

{{comp-sci-stub}}