Textbook: none required.
Syllabus in postscript and pdf.
Homework schedule: (to be filled in)
Homework 1 due 9/3
Homework 2 due 9/15
Homework 3 due 9/29
Homework 4 due 10/15
Homework 5 due 10/29
Homework 6 due 11/24
Slides from class:
Introduction, graph algorithms review
See below for the introductory max-flow/min-cut slides
Edmonds-Karp analysis, Push-relabel algorithm
Min-cost flow
Gomory-Hu trees
Matchings
IP/LP Formulations
Minimum cut formulation: slides and
paper
LPs for max flow and mincut (short writeup): here.
Some LP model and data files: here.
A model for origami here
(paper with explanations).
Other notes:
Graph representation
by Jeff Erickson.
Minimum spanning trees
by Jeff Erickson.
Single-source shortest paths
by Jeff Erickson.
Max-flow/min-cut slides from CSE 450
On-line books:
Graph Theory by Reinhard Diestel.
Lecture notes:
A Course in Combinatorial Optimization and Advanced Graph Theory
and Combinatorial Optimization by
Alexander Schrijver
Algorithm applets:
DFS,
BFS,
Several graph algorithms