Augmenting Path

A path constructed by repeatedly finding a path of positive capacity from a source to a sink and then adding it to the flow (Skiena 1990, p. 237).

An augmenting path for a matching M is a path with an odd number of edges e_1, e_2, ..., e_m such that e_(odd) not in M and e_(even) in M. The symmetric difference of M with {e_i}yields a matching having one more edge than M. Augmenting paths are used in the blossom algorithm and Hungarian maximum matching algorithm for finding graph maximum matchings.

See also

Berge's Theorem, Blossom Algorithm, Hungarian Maximum Matching Algorithm

Explore with Wolfram|Alpha


Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ: Princeton University Press, 1962.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Referenced on Wolfram|Alpha

Augmenting Path

Cite this as:

Weisstein, Eric W. "Augmenting Path." From MathWorld--A Wolfram Web Resource.

Subject classifications