Chapter 7: Network Flow

This chapter focuses on algorithms that expand on the Bipartite Matching problem. It creates a polynomial-time algorithm for a general problem, which is the Maximum-Flow Problem, and shows that this is an efficient algorithm for the Bipartite Matching as well.

In this, we want to find the flow that gives us the maximum possible value. The maximum value will equal the bottleneck rate, or minimum cut, which is the minimum capacity of the path. We push flow over the paths at the maximum amount of value that we can, going back and forth until we reach the maximum-flow for the path over all of the nodes.