Next: Course requirements
Up: Course homepage: 0515.4009 Network
Previous: Course homepage: 0515.4009 Network
The course will cover most of the following topics:
- Maximum Flow: The Goldberg-Tarjan Push-Relabel max-flow algorithm
- Minimum cuts: Gomory-Hu tree cuts, global minimum cuts
- Min-Cost Flow: cancellation of negative cycle, capacity scaling,
min cycle mean, overview of Goldberg-Tarjan algorithm
- Matchings in undirected graphs: Edmonds algorithm for the unweighted case.
- Coloring: greedy vertex coloring and edge coloring.
- Connectivity: Menger's Theorem.
- Linear Programming: Farkas' Lemma, duality, complementary
slackness, Simplex algorithm.
- If time permits, some of these topics: PTAS for fractional
covering/packing, online covering/packing, separator theorem for