Research Institute for Discrete Mathematics

Lecture Course "Combinatorial Optimization"

Winter 2007/08


News: On Thursday, November 22nd, the lecture starts at 16:15 in the seminar room, and there are no exercise classes.


This course will serve two purposes:

First, it is suitable for students in the Diploma programs who have already attended courses like "Diskrete Mathematik I/II" or "Mathematische Optimierung I/II". The course will have very small intersection with these courses; rather some basic results proved in these courses (e.g. network flows) will be used to prove more advanced results in combinatorial optimization. Thus this course is the ideal continuation of either (or both) of the courses "Diskrete Mathematik I/II" and/or "Mathematische Optimierung I/II".

Second, this is the introductory course in area C (Discrete Mathematics) of the Master's Program in Mathematics and should be attended by beginning master's students (unless they focus on other areas). Basic knowledge in combinatorial algorithms, in particular network flows, is required.

This course covers the following topics: connectivity in graphs, Gomory-Hu trees, Edmonds' weighted matching algorithm, generalized matching problems, T-joins and T-cuts, disjoint paths, Steiner trees, network design, submodular functions. Some additional topics may be covered as well, including very recent results.

This course is in English. Most of it will be based on the following book:

Another very recommendable (and very comprehensive) book covering many (but not all) of the topics is:


Class Hours: Tuesdays and Thursdays 2-4 pm (14:15-15:45)
Room: Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)
First Class: October 16, 2007
Exercise Classes: J. Maßberg, Thursdays 4-6 pm (16:00-17:30)


Prof. Dr. J. Vygen