Algorithmische Graphentheorie
Sommersemester 2021
-
-
Vorlesung: im Schnitt eine Vorlesung pro Woche
Mittwochs, 14:00–15:30
Freitags, 10:00–11:30
Ü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 maximaler unabhängiger Mengen und maximaler 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
Bitte per E-Mail einen Termin vereinbaren unter sekr-wagner@ira.uka.de mit Angabe des Namens, der Matrikelnummer und des Wunschtermins.
Termine
| Mi | | Fr | |
| 14.04. | 1. Vorlesung | 16.04. | 2. Vorlesung |
| 21.04. | 3. Vorlesung | 23.04. | - |
| 28.04. | 1. Übung | 30.04. | 4. Vorlesung |
| 05.05 | 5. Vorlesung | 07.05. | 6. Vorlesung |
| 12.05. | 2. Übung | 14.05. | - |
| 19.05. | 3. Übung | 21.05. | 7. Vorlesung |
| 26.05. | - | 28.05. | - |
| 02.06. | 8. Vorlesung | 04.06. | - |
| 09.06. | 4. Übung | 11.06. | 9. Vorlesung |
| 16.06. | 10. Vorlesung | 18.06 | 11. Vorlesung |
| 23.06. | 12. Vorlesung | 25.06. | 5. Übung |
| 30.06. | 13. Vorlesung | 02.07. | - |
| 07.07. | 6. Übung | 09.07. | 14. Vorlesung |
| 14.07. | 15. Vorlesung | 16.07. | 7. Übung |
| 21.07. | 16. Vorlesung | 23.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. |
