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 |
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 |
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 |
Type | Attendance (h/Wk.) |
---|---|
Lecture | 2 |
Exercises (whole course) | 2 |
Exercises (shared course) | 0 |
Tutorial (voluntary) | 0 |
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 |
© 2022 Technische Hochschule Köln