Vorlesung: Graphalgorithmen
Dozent: Prof. Johannes Köbler
Übung: Frank Fuhlbrück
Beginn: VL: 17.10., UE: 25.10.
Eintragen über: Agnes
Übungspunkte im: Moodle-Kurs (PW in VL+UE)
| Termine: | VL Mo 15-17 (RUD 26, 1'307) VL Mi 15-17 (RUD 26, 1'307) UE Do 13-15 (RUD 26, 1'303) |
| 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:
- kürzeste und längste Pfade
- Flüsse und Schnitte
- Zusammenhang
- Matchingprobleme
- Knoten- und Kantenfärbungen
- und Planarität
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. Oldenbourg Wissenschaftsverlag, 2010
- 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. Spektrum Akademischer Verlag, Heidelberg, 2012
- Y. Dinitz: Dinitz’ Algorithm: The Original Version and Even’s Version, 2006