Mathematical Building, Room 611AB, Budapestlaan, de Uithof, Utrecht.
Monday 10.15 - 12.00, November 12-December 15 and January 19-February 9.
The course will be based on parts of the Lecture Notes: A Course on Combinatorial Optimization by A. Schrijver (abbreviated below as [LNAS]).
Additional material which will be made available through the course (links for download will be posted below).
Take home problems will be distributed on a weekly basis and will be posted below.
The exercises can be handed in after the end of the course.
The deadline to send the exercises is April 1.
Please mail a print or email them (pdf file, no doc file) at the following address:
Monique Laurent, CWI, Science Park 123, 1098 XG Amsterdam
M.Laurent at cwi dot nl
Lecture about Chapter 6 and Chapter 7.1 in [LNAS].
The exercises can be found here.
Monday November 24:
Lecture about Chapters 7.2, 7.3 and part of 7.4 in [LNAS].
Exercises 7.12, 7.19, 7.21, 7.22.
Monday December 1:
Lecture about Chapters 7.4 and 7.5 in [LNAS].
Before the next lecture please read Chapter 1 in these SDO Lecture Notes, abbreviated below as [SDO].
Exercises 7.29 and 7.32 in [LNAS] and Exercises 1.1 and 1.2 in [SDO].
Hints for Exercise 7.29 can be found here.
If you are interested to read more about chordal graphs (and the related concepts of partial k-trees and tree-width of graphs) you may look at the following short surveys by Heggernes and by Bodlaender.
Monday December 8:
Lecture about Chapter 2.1 and Chapter 3.2.
Please read also Chapters 2.2 and 2.3.
Exercices 2.1, 2.2, 2.3, 2.4 in [SDO].
Monday December 15:
Lecture about Chapters 3.3, 3.4, 3.5. Please read also Chapter 3.7.
Exercises 3.1, 3.2, 3.3 in [SDO].
Monday January 19:
Lecture about Chapters 3.6, 3.8 and part of 4.1. [Small updates have been made in these chapters in the SDO Lecture Notes].
Exercises 3.4, 3.5 and 4.2 in [SDO].
Monday January 26:
Lecture about Chapter 4.1-4.2 (small updates made in [SDO]).
Exercises 4.3, 4.4, 4.5, 4.6 in [SDO].
Monday February 2:
Unfortunately this lecture is cancelled (as there are no trains to/from Utrecht).
Monday February 9:
Lecture about Sections 4.3 and 4.4 (small updates made in these sections in [SDO]).
Exercises 4.7 and 4.8 in [SDO].