Veranstaltung

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 und erkennen lassen, sowie Werkzeuge zum Entwurf von spezialisierten Algorithmen für diese vorgestellt.

Lernziele:
Die Studierenden kennen grundlegende Begriff der algorithmischen Graphentheorie und die in diesem Zusammenhang wichtigsten Graphklassen und deren Charakterisierungen, nämlich perfekte Graphen, chordale Graphen, Vergleichbarkeitsgraphen, sowie Intervall-, Split-, und Permutationsgraphen. Sie können zudem Algorithmen zur Erkennung dieser Graphen sowie zur Lösung grundlegender algorithmischer Probleme auf diesen Graphen exemplarisch ausführen und analysieren. Außerdem sind sie in der Lage in angewandten Fragestellungen Teilprobleme zu identifizieren, die sich mittels dieser Graphklassen ausdrücken lassen, sowie Algorithmen für neue, zu Problemen aus der Vorlesungen verwandte Problemstellungen auf diesen Graphklassen zu entwickeln.

Empfehlungen:
Kenntnisse zu Grundlagen aus der Graphentheorie und Algorithmentechnik sind hilfreich

Arbeitsaufwand: Vorlesung mit 3SWS, 5LP
5 LP entspricht ca. 150 Arbeitsstunden, davon
ca. 45h Vorlesungsbesuch
ca. 60h Nachbereitung und Bearbeitung der Übungsaufgaben
ca. 45h Prüfungsvorbereitung

Die Erfolgskontrolle erfolgt in Form einer mündlichen Prüfung nach § 4 Abs. 2 Nr. 2 SPO.

Die Lehrveranstaltung wird unregelmäßig angeboten.