The authors of the text has a webpage for the book including a list of typographical errors.
Lectures
Jan 3: Review of LP: Fourier-Motzins Elimination, Farkas' Lemma.
Jan 8: Review of LP: Farkas' Lemma, Strong Duality Theorem, Fundamental Theorem of Linear Programming, Complementary Slackness.
Jan 10: Minimum weight spanning tree problem, Kruskal's algorithm, Prim's algorithm, basic polyhedral concepts.
Jan 15: Basic polyhedral concepts, spanning tree polytope
Jan 17: Shortest paths, feasible potentials, Ford algorithm. Jan 17: Shortest paths, feasible potentials, Ford algorithm, Bellman-Ford algorithm.
Jan 22: Linear programming and shortest path, Dijkstra's Algorithm, maximum flow and minimum cut problems.
Jan 24: Ford-Fulkerson Algorithm, max-flow-min-cut theorem.
Jan 29: Edmonds-Karp modification, duality proof of the max-flow-min-cut theorem, complementary slackness proof of the max-flow-min-cut theorem.
Jan 31: Another proof of the max-flow-min-cut theorem, Gale's Theorem, Hoffman's Theorem.
Feb 5: More feasibility results, min-flow-max-cut theorem, Konig's Theorem, Hall's Theorem.
Feb 7: Perfect matching algorithm for bipartite graphs, weighted perfect matching algorithm for bipartite graphs.
Feb 12: Maximum cardinality matching algorithm for bipartite graphs, weighted matching algorithm for bipartite graphs, Tutte's Theorem, perfect matching algorithm for general graphs.
Feb 14: Weighted perfect matching algorithm for general graphs, Tutte-Berge Formula, maximum cardinality matching for general graphs.
Feb 26: Midterm Test.
Feb 28: Edmonds-Gallai Decomposition, maximum weight matching for general graphs.
Mar 5: VLSI presented by Professor Steffy.
Mar 7: Anderson's proof of Tutte's Theorem, Schrijver's proof of Tutte-Berge Formula, equivalency between Tutte's Theorem and Tutte-Berge Formula.
Mar 12: Minimum Cost Flow Problem, optimality condition, negative cycle cancellation algorithm (basic version, pseudo polynomial).
Mar 14: Primal-Dual minimum cost flow algorithm (basic version, pseudo polynomial), reduction to the transshipment problem.
Mar 19: Successive Scaling Algorithm for minimum cost flow problem (polynomial time).
Mar 21: Scale-and-Shrink minimum cost flow problem (strongly polynomial time), Gomory-Hu trees.
Mar 26: Special office hours.
Mar 28: Chinese Postman Problem, Karger's Algorithm for finding unrestricted minimum cuts.
April 2: Node identification algorithm for finding unrestricted minimum cuts, weighted T-join problem.
April 4: Seymour's min-max theorem on packing T-cuts in bipartite graphs, Lovasz' Theorem.
April 9: Augmentation problems, Frank's algorithm.
April 11: Lovasz' Splitting Off Theorem.
April 16: Successive augmentation problem for undirected graph, edge connectivity version.