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

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