MATH 8500 Algorithmic graph theory
Spring, 2017
Intructors:
Anastasios Sidiropoulos
Time:
Mon Wed Fri, 3:00-3:55pm
Location:
Enarson Classroom Bldg 340
Office hours:
TBA
Syllabus
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
Project
Suggested topics.
Schedule for project presentations.
Lectures
-
Jan 9, 2017. Lecture 1: Min-Cut and k-Cut. [Lecture notes by Ario Salmasi]
-
Jan 11, 2017. Lecture 2:
Multiway Cut.
[Lecture notes by Austin Alan Antoniou]
-
Jan 13, 2017. Lecture 3:
Max-Cut and Szemeredi's Regularity Lemma.
[Lecture notes by Dhanvi Sriram Athmakuri]
-
Jan 20, 2017. Lecture 4:
Max-Cut and Szemeredi's Regularity Lemma (cont.).
[Lecture notes by Jason Bello]
-
Jan 23, 2017. Lecture 5:
Max-Cut and Szemeredi's Regularity Lemma (cont.).
[Lecture notes by Timothy Carpenter]
-
Jan 25, 2017. Lecture 6:
Maximum Bipartite Matching.
[Lecture notes by Sherif ElAzzouni]
-
Jan 27, 2017. Lecture 7:
Maximum Matching.
[Lecture notes by Elena Farahbakhsh]
-
Feb 1, 2017. Lecture 8 [scribe Tianqi Li].
Christofides algorithm for TSP.
-
Feb 3, 2017. Lecture 9:
Treewidth.
[Lecture notes by Francisco Martinez]
-
Feb 6, 2017. Lecture 10 [scribe Akshay Mehra].
Treewidth and dynamic programming.
-
Feb 8, 2017. Lecture 11 [scribe Joseph Phelps].
Treewidth and grids.
-
Feb 10, 2017. Lecture 12 [scribe Saurabh Singh].
Treewidth and subexponential-time algorithms on planar graphs.
-
Feb 13, 2017. Lecture 13. TSP on directed planar graphs [guest lecture by Ario Salmasi].
-
Feb 15, 2017. Lecture 14. TSP on directed planar graphs (cont.).
-
Feb 17, 2017. Lecture 15. TSP on the plane [guest lecture by Vijay Sridhar].
-
Feb 20, 2017. Lecture 16 [scribe Kritika Singhal].
Treewidth, bidimensionality, and subexponential-time algorithms on planar graphs.
-
Feb 24, 2017. Lecture 17.
Treewidth, bidimensionality, and subexponential-time algorithms on planar graphs (cont.).
-
Feb 27, 2017. Lecture 18 [scribe Ryan Slechta].
Baker's technique.
-
Mar 1, 2017. Lecture 19 [scribe Vijay Sridhar].
Baker's technique (cont.).
-
Mar 3, 2017. Lecture 20 [scribe Ross Vasko].
Baker's technique (cont.).
-
Mar 6, 2017. Lecture 21 [scribe Sinong Wang].
Sparsest-Cut and balanced cuts.
-
Mar 8, 2017. Lecture 22 [scribe Dingkang Wang].
Divide and conquer using balanced cuts.
-
Mar 10, 2017. Lecture 23 [scribe Han Yu].
Approximating Crossing Number and Graph Genus.
-
Mar 20, 2017. Lecture 24 [scribe Qi Zhao].
Approximating Multi-Cut.
-
Mar 22, 2017. Lecture 26.
Approximating Multi-Cut (cont.).
-
Mar 24, 2017. Lecture 27.
Approximating Multi-Cut (cont.).
-
Mar 27, 2017. Lecture 28.
Sparsest-Cut and multicommodity flows.
-
Mar 29, 2017. Lecture 29.
Sparsest-Cut and embeddings into L1.
-
Mar 31, 2017. Lecture 30.
Sparsest-Cut and embeddings into L1 (cont.).
-
Apr 3, 2017. Lecture 31.
Sparsest-Cut and embeddings into L1 (cont.).
-
Apr 5, 2017. Lecture 32.
Irrelevant vertices.
-
Robertson, N., Seymour, P. D.
Graph Minors XIII. The disjoint paths problem.
JCTB, 1995.
-
Kawarabayashi, K., Kobayashi, Y., Reed, B.
The disjoint paths problem in quadratic time.
JCTB, 2012.
-
Grohe, M.
Computing crossing numbers in quadratic time.
JCCS, 2004.
-
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.
FOCS, 2008.
-
Apr 7, 2017. Lecture 33.
Irrelevant vertices (cont.).
-
Apr 10, 2017. Lecture 34.
The Cut-Matching game.