In particular, please have a quick read over the first two chapters for Monday.

- Lecture 16: gives the notation (flows, residual graphs, augmenting paths), as well as Ford and Fulkerson's proof that max-flow = min-cut using augmenting paths.
- Lecture 17: gives examples where augmenting paths might take a long time (or converges to a non-optimal flow in graphs with non-integer capacities). Then gives two heuristics of Edmonds and Karp to ensure fast convergence.

## No comments:

## Post a Comment