Lectures and Schedule with Materials

Below you find the schedule for 2016-2017.

Links to the slides and relevant materials will be added or updated during the course.
Week nr Lecture on tuesday by Johan van Rooij Lecture on thurday by Hans Bodlaender
46
November 15th
Introduction.
Slides: PPTX, PDF.
Stable Mariage Problem.
Slides: PPTX, PDF (first part).
Further reading:
  • Kleinberg and Tardos: Chapter 1.
November 17th
Flows and Matchings I: Maximum flow
Slides: PPT, PDF.
Further reading:
  • Cormen, Leiserson, Rivest, Stein: Chapter 26
  • Ahuja, Magnanti, Orlin. Network Flows.
  • Schrijver. Combinatorial optimization. Chapters 10 and 11.
Flows and Matchings II: Minimum Cost flow.
Slides: PPT, PDF.
Further reading:
  • Ahuja, Magnanti, Orlin. Network Flows.
  • Schrijver. Combinatorial Optimization. Chapter 12.
47
November 22nd
Stable Roommates Problem.
Slides: PPTX, PDF (second part).
Further reading:
  • Robert W. Irving, An efficient algorithm for the "Stable Roommates" problem, Journal of Algorithms 6, 577-595, 1985. (ScienceDirect)
Shortest Paths: basics.
Slides: PPTX, PDF (first part).
Further reading:
  • Cormen et al.: Chapters 24 en 25.
  • Schrijver: Chapters 7 and 8.
November 24th
Flows and Matchings II.
See November 17.
48
November 29th
Advanced Shortest Paths Algorithms.
Slides: PPTX, PDF (second part).
Further reading:
  • Cormen et al.: Chapters 24 en 25.
  • Schrijver: Chapters 7 and 8.
Introduction to Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (first part).
Further reading:
  • Fomin and Kratsch: Chapters 1 and 3.
  • Sections 1-3 from: Gerard Woeginger, Exact Algorithms for NP-hard problems. "Combinatorial Optimization - Eureka! You shrink!". LNCS 2570, 185-207, 2003. (Download from TU/e).
December 1st
Flows and Matchings III.
Graph Isomorphism.
Slides: PPT, PDF.
Planar graphs.
Slides: PPTX, PDF.
Further reading:
  • Tamassia (editor): Handbook of Graph Drawing and Visualization, 2013. Online version of the book.
  • Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs (1998).
49
December 6th
Some Techniques for Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (second part).
Further reading:
  • Fomin and Kratsch: Chapters 2, 8, 9
  • Sections 4-6 from: Gerard Woeginger, Exact Algorithms for NP-hard problems. "Combinatorial Optimization - Eureka! You shrink!". LNCS 2570, 185-207, 2003. (Download from TU/e).
Inclusion/Exclusion.
Slides: PPTX, PDF (third part).
Further reading:
  • Fomin and Kratsch: Chapter 4.
  • Cygan et al.: Section 10.1.
December 8th
Graph matching.
Slides: PPT, PDF.
50
December 13th
Measure-and-Conquer Analysis for Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (fourth part).
Further reading:
  • Fomin and Kratsch: Chapter 6.
Shortest Path Algorithms for Huge Graphs.
Slides: PPTX, PDF (third part).
December 15th
Planar graphs.
Slides: PPTX, PDF.
51
December 20th
First Exam.
Topics for the exam are the topics of weeks 46-49 and the Tuesday lecture of week 50, and from the Thursday lecture of week 50, graph isomorphism of trees and force directed graph drawing.

Reminder: the exam will start at 8:30, NOT at 9:00 as the lectures. The exam takes place in EDUC-GAMMA.

December 22nd
Fixed Parameter Tractability I.
Slides: PPTX, PDF.
2
January 10rd
Approximation Algorithms
Slides: PPTX, PDF (first part).
Further reading:
  • Cormen et al.: Chapter 35.
  • Kleinberg and Tardos: Chapter 12.
The Landscape of Approximation Algorithms.
Slides: PPTX, PDF (second part).
Further reading:
  • Cormen et al.: Chapter 35.
  • Kleinberg and Tardos: Chapter 12.
  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998. Chapter 3.(download)
January 12th
Fixed Parameter Tractability II.
Slides: PPTX, PDF. The part on Iterative Improvement is not course material this year.

Background reading:
Cygan et al., Parameterized Algorithms, Springer, 2015. Chapters 2 (2.1, 2.2, 2.5); 3 (3.1, 3.5); 5.2

3
January 17th
The Landscape of Approximation Algorithms Part 2.
Slides: PPTX, PDF (third part).
Further reading:
  • Cormen et al.: Chapter 35.
  • Kleinberg and Tardos: Chapter 12.
  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998. Chapter 3.(download)
January 19nd
Treewidth I.
Slides: PPTX, PDF.

Background reading:
Cygan et al., Parameterized Algorithms, Springer, 2015. Chapter 7 (7.1, 7.2, 7.3)

4
January 24th
Parameterised Complexity.
Slides: PPTX, PDF.
Further reading:
  • Cygan et al., Parameterized Algorithms: Chapter 13.
Approximation Complexity.
Slides: PPTX, PDF (fourth part).
Further reading:
  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998. Chapter 3.(download)
January 26th
Treewidth II.
h6>Treewidth I. Slides: PPTX, PDF.
PPT, PDF. Shortest paths and treewidth.
5
Februari 2th
Second Exam.
Topics for the exam are the topics of weeks 51 - 4.