CSE 550 Combinatorial Algorithms and Intractability

Arizona State University, Fall 2009
TuTh 9:00--10:15 BYAC 260

Instructor: Goran Konjevod, BY 450; Office hours: TuTh 10:30--12:00

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
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