CS 594 Graph Algorithms
Tue Thu, 2:00-3:15pm
1:00-2:00pm, SEO 1240
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms.
R. Ahuja, L. Magnanti and J. Orlin, Network Flows: Theory, Algorithms, and Applications.
B. Mohar and C. Thomassen, Graphs on Surfaces.
Description of the intended student audience
The course will be accessible to students with some knowledge of algorithms, graph theory, discrete mathematics, and probability theory. Programming experience is not necessary.
Aug 27, 2019. Lecture 1:
Min-Cut and k-Cut.
[Lecture notes by Ario Salmasi]
Aug 29, 2019. Lecture 2:
[Lecture notes by Austin Antoniou]
Sep 3, 2019. Lecture 3:
Algorithms on dense graphs and Szemeredi's Regularity Lemma.
[Lecture notes by Dhanvi Sriram Athmakuri], [Lecture notes by Jason Bello], [Lecture notes by Timothy Carpenter]
Sep 12, 2019. Lecture 6.
Christofides algorithm for TSP.
Sep 17, 2019. Lecture 7:
Treewidth and dynamic programming.
[Lecture notes by Francisco Martinez]
Sep 19, 2019. Lecture 8:
[Lecture notes by Ryan Slechta], [Lecture notes by Ross Vasko]
Sep 24, 2019. Lecture 9.
Sep 26, 2019. Lecture 10.
Subexponential-time algorithms on planar graphs.
Oct 1, 2019. Lecture 11.
The disjoint-paths problem.
Robertson, N., Seymour, P. D.
Graph Minors XIII. The disjoint paths problem.
Kawarabayashi, K., Kobayashi, Y., Reed, B.
The disjoint paths problem in quadratic time.
Computing crossing numbers in quadratic time.
Kawarabayashi, K., Mohar, B., Reed, B.
A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width.
Algorithms on large graphs
Oct 3, 2019. Lecture 12.
Approximate transitive closure.
Oct 8, 2019. Lecture 13.
Streaming graph algorithms.
Feigenbaum, F., Kannan, S., McGrefor, A., Suri, S., and Zhang, J.
Graph Distances in the Data Stream Model.
Oct 10, 2019. Lecture 14.
Streaming graph algorithms (cont.).
Oct 15, 2019. Lecture 15.
Graph property testing.
Divide and conquer
Oct 17, 2019. Lecture 16.
Divide and conquer via sparse cuts.
Oct 22, 2019. Lecture 17.
Computing sparse cuts.
Oct 24, 2019. Lecture 18.
Computing sparse cuts (cont.).
Oct 29, 2019. Lecture 19.
Graph Neural Networks
Oct 31, 2019. Lecture 20.
Graph Neural Networks.
Gori, M., Monfardini, G., Scarselli, F.
A new model for learning in graph domains.
Dai, H., Khalil, E., Zhang, Y., Dilkina, B., Song, L.
Learning Combinatorial Optimization Algorithms over Graphs.
Nov 5, 2019. Lecture 21.
Vinyals, O., Fortunato, M., Jaitly, N.
Smith, W. D., Wormald, N. C.
Geometric separator theorems and applications.
Nearly linear time approximation schemes for Euclidean TSP and other geometric problems.
Simplification of graphs
Nov 7, 2019. Lecture 22.
Nov 12, 2019. Lecture 23.
Random embeddings (cont.).
Nov 14, 2019. Lecture 24.
Random embeddings that preserve capacities.