CS369: Advanced Graph Algorithms
Instructor: Tim
Roughgarden (Office hours: Thursdays 1-2 PM in Gates 462)
Teaching Assistant:
Shaddin Dughmi (Office hours: Tue 1:15-2:15 PM and Wed 11-Noon in Gates 460;
Email: shaddin "at" cs)
Time/location:
2:15-3:30 PM on Tuesdays and Thursdays in Gates B12.
Course description:
Fast algorithms for fundamental graph optimization problems, including
maximum flow, minimum cuts, minimum spanning trees, nonbipartite
matching, planar separators and applications, and shortest paths.
Data structures including Fibonacci heaps, splay trees, and dynamic
trees. Tools from linear programming, matroid theory, minmax
theorems, polytope theory, and random sampling.
Pre- or corequisite: CS261 or equivalent.
Course requirements: 4 problem sets and a take-home final.
Students taking the course for credit should attempt 4 of 5 problems
on each.
Students taking the course pass/fail should attempt 2 of 5 problems
on each.
No late assignments accepted.
General references: The following are on two-hour reserve at
the Math-CS library.
- Cook/Cunningham/Pulleyblank/Schrijver, Combinatorial Optimization.
- Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms.
- Korte/Vygen, Combinatorial Optimization.
- Kozen, Design and Analysis of Algorithms.
- Papadimitriou/Steiglitz, Combinatorial Optimization.
- Schrijver, Combinatorial Optimization: Polyhedra and
Efficiency.
- Tarjan, Data Structures and Network Algorithms.
Detailed schedule and references:
- Tue 1/8: Review of Prim's MST Algorithm. Binomial heaps.
Textbook references:
- Kozen Chapter 8; CLRS Chapter 19.
Historical references:
- Thu 1/10: Fibonacci heaps. O(m + n log n) and O(m log* n) MST
algorithms.
Textbook references:
Historical references:
- Tue 1/15: Boruvka's algorithm. The Karger-Klein-Tarjan algorithm.
Textbook references:
Historical references:
- Thu 1/17: MST Verification with only linear comparisons.
Textbook references:
Historical references:
For the state-of-the-art in deterministic MST algorithms, see:
- Fredman/Willard, Trans-dichotomous
algorithms for minimum spanning trees and shortest paths, JCSS '94.
- Chazelle, A
minimum spanning tree algorithm with inverse-Ackermann type complexity, JACM '00.
- Chazelle, The soft heap: an approximate priority queue
with optimal error rate, JACM '00.
- Pettie, Finding
Minimum Spanning Trees in O(m alpha(m,n)) Time, '99 tech report.
- Pettie/Ramachandran, An optimal minimum spanning tree algorithm, JACM '02.
- Tue 1/22: Introduction to shortest paths.
Start Goldberg's O(\sqrt{n}m log C) algorithm for single-source
shortest paths with negative edge lengths.
- Thu 1/24: Finish Goldberg's algorithm.
- Tue 1/29: Seidel's O(M(n) log n) algorithm for all-pairs
shortest-paths in undirected unweighted graphs.
- Thu 1/31: The planar separator theorem.
Textbook references:
Original paper:
- Tue 2/5: More planar graph algorithms. Linear-time
5-coloring; quadratic-time planarity testing.
Textbook reference:
The first linear-time planarity test:
The most recent linear-time planarity testing algorithm:
- Thu 2/7: Edmonds's maximum-cardinality (nonbipartite)
matching algorithm. Textbook references:
- Section 5.2 of the Cook et al book; Section 9.3 of Tarjan's book.
Original paper (stop by if you want a copy):
- Edmonds, "Paths, Trees, and Flowers", Canadian Journal of
Mathematics, 17:449-467, 1965.
- Tue 2/12: Fast implementation of Edmonds via
Union-Find. Same references as above and also:
- Thu 2/14: Optimal Union-Find:
The original O(m\sqrt{n}) algorithm for maximum matching:
A newer algorithm with the same run time:
Randomized algorithms based on the Tutte matrix:
- Motwani/Raghavan, Randomized Algorithms, Sections 7.2, 7.3,
and 12.4.
- For a derandomization, see:
Geelen, An Algebraic
Matching Algorithm, Combinatorica '00.
- Tue 2/19: State-of-the-art in randomized maximum matching algorithms.
- Thu 2/21: Fast Gaussian elimination.
A primal-dual approach to minimum-cost perfect matching.
- For example, Section 5.3 of the Cook et al. book.
- Tue 2/26:
Edmonds's algorithm for min-cost perfect matching.
Original reference:
- Edmonds, "Maximum matching and a polyhedron with 0,1-vertices",
Journal of Research of the National Bureau of Standards, Series B, '65.
Textbook treatments:
- For example, Section 5.3 of Cook et al.
or Section 11.3 of Papadimitriou/Steiglitz.
- Thu 2/28: Gomory-Hu trees.
Original reference:
Textbook treatments:
- For example, Section 3.5 of Cook et al.
or Section 15.4 of Schrijver.
- Tue 3/4: Deterministic and randomized graph
sparsification. Applications to s-t cuts and flows.
- Thu 3/6: Finish random sparsification and applications.
Main reference: the Benczur-Karger paper above. For more applicatons of the
Compression Theorem to computing s-t cuts and flows, see both the
Benczur-Karger paper and also:
- Tue 3/11: The Goldberg-Rao maximum flow algorithm.
Primary reference:
Historical references:
- Thu 3/13: Finish the Goldberg-Rao algorithm.
(Same references as last lecture.)