Algorithmische Graphentheorie
Wintersemester 2014
- Dozenten: Dr. Ignaz Rutter
- Übungsleiter: Dr. Thomas Bläsius
- Vorlesung: (im Schnitt eine Vorlesung pro Woche)
- Mittwochs, 14:00–15:30, SR 236, Gebäude 50.34 - Informatikgebäude
- Donnerstags, 9:45–11:15, SR 131, 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 IN4INDAA geprüft werden
- Prüfung: Die Prüfung erfolgt mündlich in der vorlesungsfreien Zeit nach Semesterende. Die Termine werden rechtzeitig hier bekannt gegeben.
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.
Neueste Meldungen
14.10.2014: Veranstaltungstermine eingetragen.
31.7.2014: Homepage zur Vorlesung ist online. Weitere Informationen folgen.
Prüfung
Die Prüfungen finden am 26.2.2015 und am 9.4.2015 jeweils von 9:00 bis 13:00 statt. Anmeldung bitte rechtzeitig (mindestens eine Woche vor der Prüfung) per Mail an rutter [at] kit [dot] edu.
Termine
| Mi | Do | ||
|---|---|---|---|
| 22.10. | 1. Vorlesung | 23.10. | 2. Vorlesung |
| 29.10. | 1. Übung | 30.10. | |
| 5.11. | 3. Vorlesung | 6.11. | |
| 12.11. | 4. Vorlesung | 13.11. | 2. Übung |
| 19.11. | 5. Vorlesung | 20.11. | |
| 26.11. | 6. Vorlesung | 27.11. | 3. Übung |
| 3.12. | 4.12. | 7. Vorlesung | |
| 10.12. | 8. Vorlesung | 11.12. | 4. Übung |
| 17.12. | 9. Vorlesung | 18.12. | |
| Weihnachtspause | |||
| 7.1. | 10. Vorlesung | 8.1. | |
| 14.1. | 11. Vorlesung | 15.1. | 5. Übung |
| 21.1. | 12. Vorlesung | 22.1. | 13. Vorlesung |
| 28.1. | 29.1. | 6. Übung | |
| 4.2. | 14. Vorlesung | 5.2. | |
| 11.2. | 15. Vorlesung | 12.2. | 7. Übung |
Folien und Skripte
Eine Sammlung von Vorlesungsnotizen (nur für Hörer zugänglich) entsteht parallel zur Vorlesung.
Übungen
Es wird regelmäßig Übungsblätter geben, diese werden teilweise im Rahmen der Übungstermine besprochen.
Übungsblätter
| Ausgabe | Besprechung | Blatt |
|---|---|---|
| 22.10. | 29.10. | Übungsblatt 1 |
| 29.10. | 13.11. | Übungsblatt 2 |
| 13.11. | 27.11. | Übungsblatt 3 |
| 27.11. | 11.12. | Übungsblatt 4 |
| 11.12. | 15.01. | Übungsblatt 5 |
| 15.01. | 29.01. | Übungsblatt 6 |
| 29.01. | 12.02. | Übungsblatt 7 |
| 12.02. | - | Übungsblatt 8 |
Sonstige Übungsmaterialien
- "Cheat Sheet": Die wichtigsten Parameter auf einen Blick
- Übung 3: Folien zur Vorbereitung auf Aufgabe 7 von Übungsblatt 3
Literatur
| Allgemeine Einführung in die Graphentheorie | |
|---|---|
| [Die10] | Reinhard Diestel, Graph Theory, Springer, 2010. |
| Grundlegende Graphenalgorithmen | |
|---|---|
| [KN12] | Sven Oliver Krumke, Hartmut Noltemeier, Graphentheoretische Konzepte und Algorithmen, Springer Vieweg, 2012. |
| [CLRS12] | Thomas H. Formen, 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. |