Vorlesung: Graphalgorithmen
Dozent: Prof. Dr. Johannes Köbler
Beginn: VL: 17.10., UE: 26.10.
Eintragen über: Agnes
VL+UE im: Moodle-Kurs (PW in der ersten Vorlesung)
| Termine: | VL Di 15-17 RUD25 3.101 VL Do 15-17 RUD25 3.101 UE Do 13-15 RUD25 3.113 |
| Zuordnung: |
Master (M.Sc.): Modul |
Inhalte und Lernziele
Viele praktisch relevante Problemstellungen lassen sich durch graphentheoretische Probleme modellieren. Während sich die Graphentheorie vorwiegend der Erforschung kombinatorischer Eigenschaften von Graphen widmet, steht in diesem Modul der Entwurf von effizienten Algorithmen auf Graphen im Mittelpunkt. Dabei werden wir sehen, dass sich nicht nur graphentheoretische Resultate bei der Suche nach effizienten Algorithmen gewinnbringend anwenden lassen, sondern auch umgekehrt der Algorithmenentwurf zu neuen interessanten graphentheoretischen Fragestellungen führt. Konkret werden wir uns unter anderem mit folgenden Themen befassen:
- Knoten- und Kantenfärbungen
- Planarität
- Chordale Graphen
- Flüsse in Netzwerken
- Matchingprobleme
- Baum- und Pfadweite
Da viele algorithmische Graphprobleme NP-hart sind, gehen wir auch der Frage nach, auf welchen eingeschränkten Graphklassen eine effiziente Lösung möglich ist.
Empfohlene Literatur
- T. Cormen, C. Leiserson, R. Rivest, C. Stein: Algorithmen - Eine Einführung. De Gruyter Oldenbourg, 2017
(Dieses Buch ist für HU-Angehörige abrufbar, Sie müssen sich aber mit dem HU-Account dort per SSO einloggen, Zugriff aus dem HU-Netz genügt nicht.) - R. Diestel: Graphentheorie. Springer-Lehrbuch, 2016. Free Preview (englische Ausgabe 2016)
- J. Kleinberg, E. Tardos: Algorithm Design. Pearson, Addison-Wesley 2006
- V. Turau: Algorithmische Graphentheorie. Oldenbourg Wissenschaftsverlag, 2009
- T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. Springer Vieweg, 2017
- Y. Dinitz: Dinitz’ Algorithm: The Original Version and Even’s Version, 2006