Hopcroft–Karp algorithm: Difference between revisions

Revision as of 22:41, 5 March 2009

Revision as of 22:41, 5 March 2009

Line 28:

Therefore, the first √''n'' phases, in a graph with ''n'' vertices and ''m'' edges, take time O(''m'' √''n'').

It can be shown that each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once thisthe numberinitial √''n'' phases of initialthe phasesalgorithm isare complete, the shortest remaining augmenting path has at least √''n'' edges in it. However, the eventual optimal matching differs from the partial matching ''M'' found by the initial phases in a collection of vertex-disjoint augmenting paths and alternating cycles. If each of the paths in this collection has length at least √''n'', there can be at most √''n'' paths in the collection, and the size of the optimal matching can differ from the size of ''M'' by at most √''n'' edges. Since each phase of the algorithm increases the size of the matching by at least one, there can be at most √''n'' additional phases before the algorithm terminates.

Since the algorithm performs a total of at most 2√''n'' phases, it takes a total time of O(''m'' √''n'').