Vorlesung: Graphalgorithmen
Dozent: Sebastian Kuhnert
Übung: Frank Fuhlbrück
| Termine: |
VL Mo 11-13 (RUD 26, 1'306) VL Mi 13-15 (RUD 26, 1'305) UE Mi 15-17 (RUD 26, 1'305) |
| Zuordnung: |
Master (M.Sc.): Modul Diplom-Hauptstudium: Halbkurs |
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
- Färbung
- 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 Masterclass, 2006. Elektronische Ausgabe, 2000.
- 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