This course will serve two purposes:
First, this is the introductory module in area C (Discrete Mathematics) of the Master's Programme in Mathematics and an introductory module in the area "Algorithmics" of the Master's Programme in Computer Science. This course 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.
Second, the course is suitable for students in the Diploma programmes who have already attended courses like "Diskrete Mathematik I/II" or "Mathematische Optimierung I/II" or discrete mathematics courses of the new bachelor's programmes. The course will have very small intersection with these courses; rather some basic results proved in these courses (e.g., on network flows) will be used to prove more advanced results in combinatorial optimization. Thus, this course is the ideal continuation of the above-mentioned courses.
This course covers the following topics: connectivity in graphs, Gomory-Hu trees, nonbipartite matching, Edmonds' weighted matching algorithm, generalized matching problems, T-joins and T-cuts, submodular functions, network design, traveling salesman problem, polyhedral combinatorics. 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) |
| Exercise Classes: | Thursdays 6-8 pm (18:00-19:30), Gerhard-Konow-Hörsaal. More information |
| Oral Exams: | February 26, 2010 |
Prof. Dr. J. Vygen