Institut für Theoretische Informatik, Algorithmik

Algorithmische Graphentheorie

Sommersemester 2020
  • Dozenten: Torsten Ueckerdt
  • Übungsleiter: Dr. Sascha Gritzbach
  • Vorlesung: im Schnitt eine Vorlesung pro Woche
    • Mittwochs, 14:00–15:30
    • Freitags, 9:45–11:15
  • Ü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

  • Mündliche Prüfungen finden statt am: 03.08., 24.09. (ausgebucht) und 27.10.20 (ausgebucht). Zusatztermine gibt es evt. auf Anfrage.
Bitte per Email einen Termin vereinbaren unter sekr-wagner@ira.uka.de mit Angabe der Matrikelnummer.
  • Generalprobe am 17. April, 9:45 Uhr (mehr dazu im ILIAS)
Bitte vorab anmelden!

Um die Teilnehmerzahl abschätzen zu können, möchten wir Sie bitten, sich vorab (und möglichst bald) im zur Vorlesung gehörenden ILIAS-Arbeitsbereich anzumelden. Dies ist für uns wichtig, um einschätzen zu können, welche technische Lösung für unsere Video-Vorlesung die passendste ist.

Termine

Mi Fr
22.04. 1. Vorlesung 24.04. 2. Vorlesung
29.04. 3. Vorlesung 01.05. (Feiertag)
06.05. 1. Übung 08.05. 4. Vorlesung
13.05 5. Vorlesung 15.05. 2. Übung
20.05. 6. Vorlesung 22.05. -
27.05. 3. Übung 29.05. 7. Vorlesung
03.06. 8. Vorlesung 05.06. 9. Vorlesung
10.06. 4. Übung 12.06. -
17.06. 10. Vorlesung 19.06 11. Vorlesung
24.06. 12. Vorlesung 26.06. 5. Übung
01.07. - 03.07. -
08.07. 13. Vorlesung 10.07. 14. Vorlesung
15.07. 6. Übung 17.07. 15. Vorlesung
22.07. 7. Übung 24.07. -

Folien und Skripte

Unterlagen zur Vorlesung sind auf der Lernplattform ILIAS in unserem Kurs zu finden.

Übungen

Es wird regelmäßig Übungsblätter geben, diese werden teilweise im Rahmen der Übungstermine besprochen. Die Übungsblätter sind im Laufe des Semesters ebenfalls über ILIAS zu finden.

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.