Chapter 10. Matchings, Cuts, and Flows
A joyful life is an individual creation that cannot be copied from a recipe.
|--Mihaly Csikszentmihalyi, Flow: The Psychology of Optimal Experience|
While the previous chapter gave you several algorithms for a single problem, this chapter describes a single algorithm with many variations and applications. The core problem is that of finding maximum flow in a network, and the main solution strategy I'll be using is the augmenting path method of Ford and Fulkerson. Before tackling the full problem, I'll guide you through two simpler problems, which are basically special cases (they're easily reduced to maximum flow). These problems, bipartite matching and disjoint paths, have many applications themselves and ...