Blockseminar über Parametrisierte Algorithmen und Komplexität

Vorbesprechung und Scheinbedingungen

Vorbesprechung am 25. August 2006, 11.00 - 12.00 Uhr, Pohligstr.1, Raum 616. In diesem Rahmen werden auch die Themen vergeben.

Scheinbedingung ist die Ausarbeitung eines Referats samt Vortrag von 60-90 Min. Länge. Einordnung: B/D

Termine

Das Seminar findet statt als Blockveranstaltung, am Ende des WS 2006/2007, nach Vereinbarung.

Sonstiges

Weitere Termine und Informationen werden rechtzeitig im WWW angekündigt werden.

Inhalt und Seminarthemen

Anhand einzelner Textbuchkapitel und Originalarbeiten sollen Themen zur Parametrisierten Komplexität und Algorithmik behandelt werden. Ebenso sollen konkrete parametrisierte Algorithmen zu verschiedenen Problemen vorgestellt werden.

Mögliche Grob-Themen sind:

• Parametrisierte Komplexitätstheorie und W-Hierarchie
• Techniken Parameterisierter Algorithmik
• Problem-Kernelisierungen
• Parameterisierte Algorithmen fuer graphentheoretische Probleme
• Subexponentielle Klassen und Isomorphien
• Parallele Parametrisierte Komplexitätsklassen

Literatur

• R.G. Downey und M.R. Fellows, Fixed parameter tractability and NP-completeness, Congressus Numerantium 87 (1992) 161-178.
• R.G. Downey und M.R. Fellows, Parameterized Computational Feasibility, in: P. Clote, J. Remmel (Eds.), Feasible Mathematics II, pp. 219-244, Birkhäuser, Boston, 1995.
• R.G. Downey und M.R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999.
• R.G. Downey, M.R. Fellows und U. Stege, Parameterized Complexity: A framework for systematically confronting computational intractability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 49, 1999.
• J. Flum, M. Grohe, Parameterized Complexity Theory, Springer-Verlag, New York, 2006.