This is an old revision of the document!
Table of Contents
Chapter 7: Network Flow
Essentially a return to bipartite matching, this chapter extends the special case of the Bipartite Matching Problem to other matching problems such as the mapping of customers to stores. We recall the definitions of matching and perfect matching, which are, respectively, “collections of pairs over a set,” and a matching for which “every node appears in exactly one edge.” We will construct polynomial algorithms to solves these problems.
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
Set-up: Explains the terminology for flow problems. Describes the two conditions that define flow (capacity and conservation). The structure of a flow network determines its maximum value (value = flow generated at source) of a flow.
Problem outline: Find a maximum flow in a network. Sometimes single s-t paths don't support maximum flow…in these cases we might want to “push forward” on edges with residual capacity, or “push backward” on edges that already have some flow.
