Graph-Theoretic Algorithms
Spring 2017
Schedule
Graph-Theoretic Algorithms
|
|
| Home | Outline | Resources | Schedule | Summaries | Assignments | Project | Exams |
This is a preliminary schedule. The order of topics may well change.
There will be no class on May 23 (a Tuesday, but on a Monday schedule). Some later classes will also be cancelled, but consider these dates tentative. (And keep these dates free, as they will be used for 1-on-1 meetings regarding assignments and projects.)
The reference means the lecture notes. However, the lecture notes may change throughout the term, sometimes even getting new chapters. Use with caution.
| Lecture | Content | Reference |
|---|---|---|
| Lecture 1 (Mon, May 01, 2017) | Administrivia. Intro to planar graphs | Ch.1, Ch.2.1-2.2 |
| Lecture 2 (Wed, May 03, 2017) | Solving problems in planar graphs | Ch. 2.3, Ch. 3 |
| Lecture 3 (Mon, May 08, 2017) | Maximum Flow | Ch. 5 |
| Lecture 4 (Wed, May 10, 2017) | Planarity testing. Triangulated graphs | Ch. 6,7 |
| Lecture 5 (Mon, May 15, 2017) | Canonical ordering. 4-connected triangulations | Ch. 7 |
| Lecture 6 (Wed, May 17, 2017) | Friends of planar graphs | Ch. 8 |
| Mon, May 22, 2017 | No lecture (Victoria day) | |
| Lecture 7 (Wed, May 24, 2017) | Interval graphs and chordal graphs | Ch. 9, 10.1 |
| Lecture 8 (Mon, May 29, 2017) | Recognizing interval graphs. Tree decompositions | Ch. 10.1.3, 10.2, 11.1, 11.2 |
| Lecture 9 (Wed, May 31, 2017) | Partial k-trees and treewidth | Ch. 11.3, 11.4 |
| Lecture 10 (Mon, Jun 05, 2017) | More on treewidth. Pathwidth | Ch. 11.4, 11.5, (13), 12 |
| Lecture 11 (Wed, Jun 07, 2017) | More on pathwidth. Branchwidth | Ch. 12.1-4, 14.1-2 |
| Mon, Jun 12, 2017 | No lecture (keep free for assignment meetings) | |
| Lecture 12 (Wed, Jun 14, 2017) | Trees and dynamic programming | Ch. 15.1-3 |
| Lecture 13 (Mon, Jun 19, 2017) | Dynamic programming in partial k-trees | Ch. 15.3-5 |
| Lecture 14 (Wed, Jun 21, 2017) | Problems in partial k-trees | Ch. 15.5-7 |
| Lecture 15 (Mon, Jun 26, 2017) | k-outer-planar graphs | Ch. 16 |
| Lecture 16 (Wed, Jun 28, 2017) | Separators | Ch. 17, 18.1 |
| Mon, Jul 03, 2017 | No lecture (Canada Day observed) | |
| Lecture 17 (Wed, Jul 05, 2017) | Approximating Treewidth. Bidimensionality | Ch. 18 |
| Lecture 18 (Mon, Jul 10, 2017) | WQO and Graph Minor Theorem | Ch. 19 |
| Wed, Jul 12, 2017 | No lecture (keep free for 1-on-1 meetings) | |
| Mon, Jul 17, 2017 | No lecture (keep free for 1-on-1 meetings) | |
| Wed, Jul 19, 2017 | No lecture (and no meetings) | |
| Mon, Jul 24, 2017 | No lecture (and no meetings) |
