CSE 421 Introduction to Algorithms Winter 1999
The Network Flow Problem
Net Flow: Formal Definition
Example: A Flow Function
Max Flow via a Greedy Alg?
A Brief History of Flow
Greed Revisited
Residual Capacity
Residual Networks & Augmenting Paths
A Residual Network
An Augmenting Path
Lemma 1
Augmenting A Flow
PPT Slide
Ford-Fulkerson Method
Cuts
Lemma 2
Max Flow / Min Cut Theorem
(3) ? (1)
Corollaries & Facts
Edmonds-Karp Algorithm
BFS/Shortest Path Lemmas
Lemma 27.8 (Alternate Proof)
Augmentation vs BFS
Theorem 27.9
Corollary
Flow Integrality Theorem
Email: ruzzo@cs.washington.edu
Home Page: http://www.cs.washington.edu/education/courses/421
Other information: (c) 1998, University of Washington, CSE