Hopcroft–Karp algorithm: Difference between revisions

Revision as of 03:56, 22 April 2008

Revision as of 03:56, 22 April 2008

Line 15:

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

- An alternating path would beis 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.