Graph-Theoretic Algorithms
Spring 2024
Schedule
Graph-Theoretic Algorithms
|
|
| Home | Outline | Resources | Schedule | Summaries | Assignments | Project | Final |
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.
| 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 ) |