Revision as of 23:38, 5 March 2009 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,670 edits fix notation; add AMO reference; separate notes and references section; rm CLRS reference as it only gives it in an exercise rather than actually describing it in-text; rm nonbipartite ref ← Previous edit		Revision as of 23:43, 5 March 2009 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,670 edits more context in lede Next edit →
Line 1: ~~The~~In [[computer science]], the '''Hopcroft–Karp algorithm''' is an [[algorithm]] that finds maximum cardinality [[matching]]s in [[bipartite graph]]s. It runs in O(''m'' √''n'') time in the [[worst case analysis\|worst case]], where ''O'' invokes [[big O notation]], ''m'' is the number of edges in the graph, and ''n'' is the number of vertices of the graph. In the ~~worst~~ case of [[dense graph]]s time bound becomes O(''n''<sup>5/2</sup>). 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}}. It increases the size of the matching by a sequence of augmenting paths, a standard technique in matching algorithms, but instead of finding just a single augmenting path, the algorithm finds a maximal set of shortest augmenting paths in each iteration. As a result only O(√''n'') iterations are needed.

Hopcroft–Karp algorithm: Difference between revisions