Course Manual KOGA
Combinatorial Optimization and Graph Algorithms
PDF Course Catalog Deutsche Version: KOGA
Version: 1 | Last Change: 25.01.2020 18:25 | Draft: 0 | Status: vom verantwortlichen Dozent freigegeben
| Long name | Combinatorial Optimization and Graph Algorithms |
|---|---|
| Approving CModule | KOGA_MaTIN |
| Responsible |
Prof. Dr. Hubert Randerath
Professor Fakultät IME |
| Valid from | winter semester 2020/21 |
| Level | Master |
| Semester in the year | winter semester |
| Duration | Semester |
| Hours in self-study | 78 |
| ECTS | 5 |
| Professors |
Prof. Dr. Hubert Randerath
Professor Fakultät IME |
| Requirements | Basic knowledge in graph theory Basic knowledge in algorithmics |
| Language | German |
| Separate final exam | Yes |
Literature
Final exam
| Details | Written exam. In case of a low number of participants the exam might be oral. |
|---|---|
| Minimum standard | Normally, 50% of achievable exam point suffice to pass the exam (with a 4.0 grade) |
| Exam Type | EN Klausur |
Learning goals
| Goal type | Description |
|---|---|
| Knowledge | - Basics of Graph Theory und Combinatorial Optimization - Minimal Spanning Trees: algorithms of Kruskal, Prim und Tarjan, Greedy algorithms, matroids, Steiner trees, network design - Linear Programs: structure, modelling, normalization, Simplex algorithm, Theory of Duality - Weighted Matchings and the Routhe Inspection Problem: Weighted Matchings in Bipartite Graphs and non-bipartite Graphs, algorithms of Floyd-Warshall and Fleury - Network Flows: Network Theory Basics, Dinic's algorithms, cost-optimial flows - selected discreet and combinatorial optimization problems: Travelling Salesman, Channel Assignment Problem, scheduling problems, routing problems |
Expenditure classroom teaching
| Type | Attendance (h/Wk.) |
|---|---|
| Lecture | 2 |
| Exercises (whole course) | 2 |
| Exercises (shared course) | 0 |
| Tutorial (voluntary) | 0 |
Special requirements
| none |
| Accompanying material |
- Lineare und Netzwerk-Optimierung, H.W. Hamacher, Vieweg-Verlag - CATBOX - An Interactive Course in Combinatorial Optimization, W. Hochstättler, A. Schliep, Springer-Verlag - Graphentheoretische Konzepte und Algorithmen, S. O. Krumke, H. Noltemeier, Teubner-Verlag - Combinatorial Optimization - Polyhedra and Efficiency, A. Schrijver, Springer-Verlag Dozenten |
|---|---|
| Separate exam | No |
Bei Fehlern, bitte Mitteilung an die
Webredaktion der Fakultät IME
Webredaktion der Fakultät IME
© 2022 Technische Hochschule Köln