This page contains lecture materials for the course “Advanced Graph Algorithms” taught in Fall 2022.
If this page is not updated and you would like to gain access to some of the lecture notes, please email me.
Homework
Lectures
Lecture 1, Aug 25: Intro and Max-flow/Min-cut part 1
lec-1-blank
lec-1-completeinclass
Lecture 2, Aug 30: Max-flow/Min-cut part 2
Lecture 3, Sept 1: Graph Analysis as Linear Algebra, Linear Programming I
“Lecture 4”, Sept 6: Linear Programming and Graph Analysis II
Read Lectures 2 and the first part of lecture 3 (up until section 3.1.1 on MA orderings) from David Williamson’s Advanced Algorithms lecture notes here: http://www.davidpwilliamson.net/work/publication/williamson-03/
You may also wish to read through Lecture 1 and Lecture 4, but I’d like you to focus on Lectures 2 and 3. Another optional reference you may find helpful for reinforcing the concepts we have already covered in class is the Fundamental chapter (Chapter 2) of the Network Analysis textbook (https://link.springer.com/book/10.1007/b106453).
“Lecture 5”, Sept 8:
Watch lecture video on Totally Unimodular Matrices in Linear Programming (https://www.youtube.com/watch?v=Fmjy74c-R-I)
Lecture 6, Sept 13
Lecture 7, Sept 15
Lectures 8-9: Dense subgraph discovery
Densest subgraph discovery references
Lectures 10+: Graph clustering and Random Walks