Zum Inhalt
Fakultät für Informatik

Parametrisierte Algorithmen

Veranstaltungsnummer  
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Proseminar
Semester Sommersemester 2017
Ort und Zeit  
Vorbesprechung wird noch angekündigt
Querverbindungen DAP II, GTI
Voraussetzungen DAP II

Inhalt

In der Algorithmentheorie wird der Aufwand eines Algorithmus üblicherweise (asymptotisch) im Verhältnis zur Größe seiner Eingaben ausgedrückt. Bei Graphenalgorithmen oft auch in der Anzahl der Knoten des Graphen. Für viele algorithmische Probleme sind in dieser Betrachtungsweise nur Algorithmen mit exponentiellem Zeitaufwand bekannt.

Ein Beispiel hierfür ist das Vertex Cover Problem: Gegeben ein Graph G und eine Zahl k, fragt es, ob es eine Menge M von k Knoten gibt, so dass jede Kante des Graphen einen Knoten in M hat. Interessanterweise gibt es jedoch einen sehr simplen Algorithmus, dessen Aufwand O(n 2^k) ist, wobei n die Anzahl der Knoten des Eingabegraphen ist. Intuitiv ist der Aufwand dieses Algorithmus also "nur" schlecht in k, aber nicht in n. Anders gesagt: für Eingaben mit "kleinem" k lässt sich das Problem effizient lösen.

Solche Parametrisierungen gibt es auch für eine Reihe anderer algorithmischer Probleme. Entsprechende Algorithmen dieser Art wollen wir in dem Proseminar betrachten.

Die Vortragsthemen basieren zum Teil auf dem Buch Invitation to Fixed-Parameter Algorithms von Rolf Niedermeier, zum Teil auf dem Buch Fundamentals of Parameterized Complexity von Rodney G. Downey und Michael R. Fellows. Die dem Buch von Herrn Niedermeier zugrunde liegende Habilitationsschrift finden Sie hier: http://theinf1.informatik.uni-jena.de/~niedermr/publications.html.

Darüber können den Vorträgen weitere Bücher und Originalarbeiten zugrunde liegen.