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
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
Separate exam
none

© 2022 Technische Hochschule Köln