Course
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 |
| 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
keine/none
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
Written exam. In case of a low number of participants the exam might be oral.Learning goals
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
- 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 literature
keine/none
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
- 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
none
Bei Fehlern, bitte Mitteilung an die
Webredaktion der Fakultät IME
Webredaktion der Fakultät IME
© 2022 Technische Hochschule Köln