Graph-Theoretic Algorithms
Spring 2024
Schedule
Graph-Theoretic Algorithms
|
|
| Home | Outline | Resources | Schedule | Summaries | Assignments | Project | Final |
This is a tentative schedule; references should be approximately correct for lectures that have passed, but are still very much in flux for future lectures.The reference means the lecture notes. Caution, one of the chapters got moved during the course, the any references to Chapters 13,14,15 could be off by one.
For lack of time (and because we really should reach the separator theorem), a number of interesting topics will to be skipped, but we may have time to cover some of them in late June. If there are topics that you would especially liked to see covered, then let the instructor know by June 15. Possible topics that could be covered (in order where they fit in class) are:
| Lecture | Content | Reference |
|---|---|---|
| Lecture 1 (Mon, May 06, 2024) | Administrivia. Intro to planar graphs | Ch.1, Ch.2.1 |
| Lecture 2 (Wed, May 08, 2024) | Simple algorithms for planar graphs | Ch. 2.1, 2.2, 2.4 |
| Lecture 3 (Fri, May 10, 2024) | NP-hardness and planarity | Ch. 2.4, Ch. 3 |
| Lecture 4 (Mon, May 13, 2024) | Dual graphs. Maximum Flow in st-planar graphs | Ch. 2.3, Ch. 5.1, 5.2 |
| Lecture 5 (Wed, May 15, 2024) | Maximum Flow in planar graphs. Maximal planar graphs | Ch. 5.3, 7.1, 7.2 |
| Lecture 6 (Fri, May 17, 2024) | Canonical ordering and applications | Ch. 7.3 |
| Lecture 7 (Mon, May 20, 2024) | (IMPORTANT! Lecture on May 21 instead!) Friends of planar graphs | Ch. 8 |
| Lecture 8 (Wed, May 22, 2024) | Interval graphs and chordal graphs | Ch. 9 |
| Lecture 9 (Fri, May 24, 2024) | Friends. Recognizing chordal graphs | Ch. 9.5, 10.1 |
| Lecture 10 (Mon, May 27, 2024) | Recognizing interval graphs | Ch. 10.2-3, Ch. 6.2.2 |
| Lecture 11 (Wed, May 29, 2024) | Tree decompositions and k-trees | Ch. 11.1-11.3 |
| Lecture 12 (Fri, May 31, 2024) | Partial k-trees and treewidth. | Ch. 11.4-11.5 (skip 11.5.3) |
| Lecture 13 (Mon, Jun 03, 2024) | Series-parallel graphs | Ch. 11.5 (skip 11.5.3), Ch. 12 |
| Lecture 14 (Wed, Jun 05, 2024) | Friends of treewidth. Branchwidth | Ch. 14.1 (intro only), 14.4, Ch. 13.1-13.2 |
| Lecture 15 (Fri, Jun 07, 2024) | Branchwidth in planar graphs. DP in trees | 13.3, 14.1 (in part 3) |
| Lecture 16 (Mon, Jun 10, 2024) | Dynamic programming in partial k-trees | Ch. 14.2-4 (in part 3) |
| Lecture 17 (Wed, Jun 12, 2024) | Problems in partial k-trees. | Ch. 14.5-6 (in part 3), 14.3.1 (in part 2) |
| Lecture 18 (Fri, Jun 14, 2024) | Baker's PTAS for planar graphs | Ch. 16 |
| Lecture 19 (Mon, Jun 17, 2024) | Separator theorems | Ch. 17 |
| Lecture 20 (Wed, Jun 19, 2024) | Separators: applications and extensions | Ch. 17 |
| Lecture 21 (Fri, Jun 21, 2024) | Treewidth and separators | Ch. 18 |
| Lecture 22 (Mon, Jun 24, 2024) | Treewidth and grid-minors; conclusion | Ch. 18, Ch. 19.4 |
| Lecture 23 (Wed, Jun 26, 2024) | extra topics (planarity testing) | Ch6 |
| Lecture 24 (Fri, Jun 28, 2024) | Student presentations (Product Structure Theorem). Computing canonical ordering. | Student's lecture notes |
| Mon, Jul 01, 2024 | No lecture (Canada Day) | |
| Wed, Jul 03, 2024 | No lecture (keep free in case earlier lectures get cancelled) | |
| Fri, Jul 05, 2024 | No lecture (keep free in case earlier lectures get cancelled) | |
| Mon, Jul 08, 2024 | No lecture (keep free, finals likely scheduled here) | |
| Wed, Jul 10, 2024 | No lecture (keep free, finals likely scheduled here ) | |
| Fri, Jul 12, 2024 | No lecture (keep free, finals likely scheduled here ) |