Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Wintersemester 2015/2016
Algorithmische Graphentheorie

Algorithmische Graphentheorie

Wintersemester 2015
  • Dozenten: Dr. Ignaz Rutter
  • Übungsleiter: Dr. Marcel Radermacher
  • Vorlesung: (im Schnitt eine Vorlesung pro Woche)
    • Mittwochs, 14:00–15:30, SR 301, Gebäude 50.34 - Informatikgebäude
    • Donnerstags, 9:45–11:15, 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 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 erkennen lassen, sowie Werkzeuge zum Entwurf von spezialisierten Algorithmen für diese vorgestellt.

Neueste Meldungen

02.03.2016: Der Prüfungstermin am 18.3.2016 ist bis auf einen Platz voll. Zusätzlich ist nun auch der 17.3.2016 als Prüfungstermin möglich.
01.02.2016: Die Prüfungstermine sind online, Prüfungsanmeldung möglich. Anmeldung im Sekretariat (sekr [dash] wagner [at] ira [dot] uka [dot] de).

Prüfung

Die Prüfungen finden am 17.03.2016 (!), 18.03.2016 und am 06.04.2015 jeweils von 9:00 bis 12:00 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

Mi Do
21.10. 1. Vorlesung 22.10. 2. Vorlesung
28.10. 3. Vorlesung 29.10. 1. Übung
4.11. 5.11. 4. Vorlesung
11.11. 5. Vorlesung 12.11. 2. Übung
18.11. 6. Vorlesung 19.11.
25.11. 7. Vorlesung 26.11. 3. Übung
2.12. 8. Vorlesung 3.12.
9.12. 9. Vorlesung 10.12. 4. Übung
16.12. 17.12. 10. Vorlesung
Weihnachtspause
6.1. 7.1. 11. Vorlesung
13.1. 14.1. 5. Übung
20.1. 12. Vorlesung 21.1.
27.1. 6. Übung 28.1. 13. Vorlesung
3.2. 14. Vorlesung 4.2.
10.2. 15. Vorlesung 11.2. 7. Übung

Folien und Skripte

Eine Sammlung von Vorlesungsnotizen (nur für Hörer zugänglich) wird parallel zur Vorlesung überarbeitet und aktualisiert.

Ü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

Ausgabe Besprechung Blatt
21.10. 28.10. Blatt 1
29.10. 12.11. Blatt 2
12.11. 26.11. Blatt 3
26.11. 10.12. Blatt 4
10.12. 14.01. Blatt 5
14.01. 27.01. Blatt 6
27.01. 11.02. Blatt 7
11.02. - Blatt 8

Sonstige Übungsmaterialien

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.