Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

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

Aufgabenblätter

Skript