| Name | Office Hours | ||
| Instructor | Richard Anderson | anderson@cs.washington.edu | By appointment, Sieg 312 |
subscribe cse523
as the body of the message. The address of the mailing list is cse523@cs. Do not send subscription requests to the list itself.
1. Maximum Flows: Basic ideas Maxflow/mincut theorem Generic Augmentation Algorithm 2. Polynomial Algorithms: Capacity Scaling Shortest Augmenting Path Algorithm Dinics Algoirthm Efficient Data Structures, Dynamic Trees 3. Preflow Push Algorithms: Generic Preflow Push Algorithm FIFO Algorithm Highest Level First Algorithm Rao/Golberg Algorithm 4. Empirical and Average Case Results 5. Special Cases Unit Capacity Networks Bipartite Networks Planar Networks 6. Matching Non-bipartite Matching Determinant Tricks 7. Mincost Flow (edges have costs as well as capacities) Basic Algorithms Polynomial Time Algorithms Network Simplex Minimum Weight Matching 8. Generalized Flows (edges have multipliers which change quantity of flow). Linear Programming Solutions Combinatorial Approaches 9. Multicommodity Flow (different types of flows along edges)
If you have questions about the coruse, please contact me.