Thursday Jan 7.Optimal trees.: Prim and Kruskal Algorithms and speedups. Spanning Tree Polytope.
Week 2.
Tuesday Jan 12. Optimal Branchings and Arborescences. Algorithms and Fulkerson's Theorem.
Thursday Jan 14. Shortest Paths: Moore's Algorith; Dijsktra's; Min-Max Theorems.
Week 3.
Tuesday Jan 19th. Conservative weightings. Constrained Shortest Paths. Potentials. Difference Equations. Minimum Mean Cost Cycle.
Thursday Jan 21. Introduction to multiflows. Cut Condition. Disjoint paths. Sparsest cut and flow-cut gap.
Week 4.
Tuesday Jan 26. Multiflows: Expanders and large flow-cut gaps for undirected uniform multiflows. Compact formulation for flows. Quick review of
resiudal graphs and Ford Fulkerson method.
Thursday Jan 28. Maximum Flows: Applications (b-flows, circulations, matchings). Exponential running time. Edmonds/Karp and Dinits' Algorithms. Blocking flows.
Week 5.
Tuesday Feb 2. Global Minimum Cuts: Node identification algorithm. The random contraction method. Cut-trees.
Thursday Feb 4. Gomory-Hu Trees.
Week 6.
Tuesday Feb 9. Minimum Cost Flows: Cycle Cancelling Methods (Minimum Mean Cycle Augmentation).
Thursday Feb 11. Minimum Cost Flows: Capacity Scaling Algorithm. Introduction to Matchings (Tutte-Berge Formula).
Week 7.
Tuesday Feb 16. The Maximum Cardinality Matching Algorithm.
Thursday Feb 18. The Maximum Weight Matching Algorithm.
Week 8
Reading Break
Week 9
Tuessday March 2. The Matching Polytope. Intro to T-joins. Solving undirected shortest paths with negative weights. (Exam at night 530-7PM)
Thursday March 4. The T-join Algorithm.
Week 10
Tuesday March 9. T-joins, T-cuts and LP. b-factors and b-matchings.
