CS 594 Graph Algorithms
Fall, 2019
Intructors:
Anastasios Sidiropoulos
Time:
Tue Thu, 2:003:15pm
Location:
LC A3
Office hours:
TBA
Syllabus
Scribe list
Relevant textbooks

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.
Homework
TBA
Project
TBA
Lectures

Aug 27, 2019. Lecture 1:
MinCut and kCut.
[Lecture notes by Ario Salmasi]

Aug 29, 2019. Lecture 2:
Multiway Cut.
[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 5, 2019. Lecture 4:
Maximum Bipartite Matching.
[Jottings]
[Lecture notes by Sherif ElAzzouni]

Sep 10, 2019. Lecture 5:
Maximum Matching.
[Jottings]
[Lecture notes by Elena Farahbakhsh]

Sep 12, 2019. Lecture 6.
Christofides algorithm for TSP.

Sep 17, 2019. Lecture 7:
Treewidth.
[Lecture notes by Francisco Martinez]