Viele praktisch relevante Probleme lassen sich durch Problemstellungen auf Graphen modellieren. Während sich die Graphentheorie vorwiegend der Untersuchung kombinatorischer Eigenschaften von Graphen widmet, stehen in dieser Vorlesung effiziente Algorithmen auf Graphen im Mittelpunkt. Für den Entwurf solcher Algorithmen werden wir verschiedene Resultate der Graphentheorie herleiten, um diese dann anschließend gewinnbringend bei dem Entwurf auszunutzen. Konkret werden wir uns unter anderem mit folgenden Themen befassen:
- Kürzeste Pfade
- Minimal aufspannende Bäume
- Flüsse und Schnitte
- Matchingprobleme
https://www.uni-muenster.de/LearnWeb/learnweb2/course/view.php?id=44248
- Lehrende/r: Christian Scheffer
Semester: SoSe 2021