Chapter 7 – Network Flow

My notes on the assigned sections of Chapter 6 of Algorithm Design by Jon Kleinberg and Éva Tardos. This chapter details network flow algorithms like Bipartite Matching and Maximum-Flow.

The max flow problem arises from having flow in transportation networks. Transportation networks model some sort of network like a highway system or a system of pipes carrying water. Each edge in the network has a capacity, and the network has both source and sink nodes. The Ford-Fulkerson algorithm finds the maximum flow of such a network, arranging the traffic to make efficient use of the available capacity. This algorithm finds such a maximum flow in no worse than O(mC) time.

Overall, I found this section fairly each to understand and fairly interesting. I'd give it a 7/10 for both.