The course contents are divided into five broad themes.
- Network Flows and Bipartite Matchings: Recap of Ford Fulkerson method and max-flow min-cut theorem. Dinitz Algorithm, and Preflow push algorithm for max-flow. Reduction from flows to bipartite matchings. Application of max-flow min-cut theorem for structural and algorithmic results.
- Non-Bipartite matchings: Edmonds Maximum Matching Algorithm, Gallai Edmonds Decomposition theorem and applications, Tutte-Berge Formula.
- Linear Programming based algorithms: Introduction to Linear Programs, formulating combinatorial problems as Linear Programs, Notion of Dual, Primal Dual technique for exact and approximate algorithms -- weighted matchings, shortest paths.
- Shortest paths problem: Min-cost flow and shortest paths, successive shortest paths algorithms, Kargers algorithm for all-pairs-shortest paths.
- Recent topics: Recent developments related to the above topics will be discussed. Some candidate topics are dynamic graph algorithms, fast algorithms for special graph classes, online algorithms, matchings in markets.