Algorithmische Graphentheorie

Sommersemester 2019
  • Dozenten: Torsten Ueckerdt
  • Übungsleiter: Sascha Gritzbach, M.Sc.
  • Vorlesung: im Schnitt eine Vorlesung pro Woche
    • Dienstags, 14:00–15:30, SR 301, Gebäude 50.34 - Informatikgebäude
    • Donnerstags, 14:00–15:30, SR 301, Gebäude 50.34 - Informatikgebäude
  • Übung: Zusätzlich wird an einigen Vorlesungsterminen eine Übung stattfinden.
  • Credits: Es werden für diese Vorlesung 5 Leistungspunkte vergeben.
  • Module: Die Vorlesung kann im Modul M-INFO-100762 geprüft werden.
  • Prüfung: Die Prüfung erfolgt mündlich in der vorlesungsfreien Zeit nach Semesterende.

Viele grundlegende, in vielen Kontexten auftauchende Problemstellungen, etwa Färbungsprobleme oder das Finden von unabhängigen Mengen und maximalen Cliquen, sind in allgemeinen Graphen NP-schwer. Häufig sind in Anwendungen vorkommende Instanzen dieser schwierigen Probleme aber wesentlich stärker strukturiert und lassen sich daher effizient lösen. In der Vorlesung werden zunächst perfekte Graphen sowie deren wichtigste Unterklasse, die chordalen Graphen, eingeführt und Algorithmen für diverse im Allgemeinen NP-schwere Probleme auf chordalen Graphen vorstellt. Anschließend werden vertiefte Konzepte wie Vergleichbarkeitsgraphen besprochen, mit deren Hilfe sich diverse weitere Graphklassen (Intervall-, Split-, und Permutationsgraphen) charakterisieren und erkennen lassen, sowie Werkzeuge zum Entwurf von spezialisierten Algorithmen für diese vorgestellt.

Aktuelles

  • 28. Juni: In der letzten Vorlesungswoche wurden die Vorlesung und die Übung getauscht. Der aktuelle Terminplan ist unten zu finden.
  • 24. Mai: Die Prüfungstermine wurden veröffentlicht.

Prüfung

Die Prüfungen finden am 7.08.2019 , 26.08.2019 (keine freien Plätze mehr) und am 24.09.2019 statt. Anmeldung bitte rechtzeitig (mindestens eine Woche vor der Prüfung) per Mail im Sekretariat (sekr [dash] wagner [at] ira [dot] uka [dot] de).

Termine

Di Do
23.04. 1. Vorlesung 25.04. 2. Vorlesung
30.04. 3. Vorlesung 02.05. -
07.05. 1. Übung 9.05. 4. Vorlesung
14.05 5. Vorlesung 16.05. 2. Übung
21.05. 6. Vorlesung 23.05. 7. Vorlesung
28.05. 3. Übung 30.05. (Feiertag)
04.06. 8. Vorlesung 06.06. 9. Vorlesung
11.06. 4. Übung 13.06. 10. Vorlesung
18.06. - 20.06 (Feiertag)
25.06. 11. Vorlesung 27.06. -
02.07. 5. Übung 04.07. -
09.07. 12. Vorlesung 11.07. 13. Vorlesung
16.07. 6. Übung 18.07. 14. Vorlesung
23.07. 7. Übung 25.07. 15. Vorlesung

Folien und Skripte

Eine Sammlung von Vorlesungsnotizen (nur für Hörer zugänglich) steht zur Verfügung. Diese entsprechen im Großen und Ganzem den Vorlesungsinhalten.

Übungen

Es wird regelmäßig Übungsblätter geben, diese werden teilweise im Rahmen der Übungstermine besprochen.

Für die Zulassung zur mündlichen Prüfung erwarten wir, dass im Rahmen der Übung die Lösung zu mindestens einer Aufgabe vorgestellt wird.

Übungsblätter

Hier stellen wir Ihnen im Verlauf der Veranstaltung die Übungsblätter zur Verfügung.

Ausgabe Besprechung Blatt
29.04. 07.05. Blatt 1
10.05. 16.05. Blatt 2
16.05. 28.05. Blatt 3
31.05. 11.06. Blatt 4
18.06. 02.07. Blatt 5
09.07. 16.07. Blatt 6
17.07. 23.07. Blatt 7

Sonstige Übungsmaterialien

Literatur

Allgemeine Einführung in die Graphentheorie
[Die17]Reinhard Diestel, Graph Theory, Springer, 2017.
Grundlegende Graphenalgorithmen
[KN12]Sven Oliver Krumke, Hartmut Noltemeier, Graphentheoretische Konzepte und Algorithmen, Springer Vieweg, 2012.
[CLRS09]Thomas H. Cormen, Charles E. Leiseren, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press, 2009.
Perfekte Graphen
[Gol04]Charles M. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004.