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:
|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