zum Inhalt springen

Seminar über Parametrisierte Algorithmen und Komplexität

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

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

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

Scheinbedingung: Ausarbeitung eines Referats samt Vortrag von 60-90 Min. Länge.

Literatur:

  • Downey, R.G.; Fellows, M.R.: Fixed parameter tractability and NP-completeness. Congressus Numerantium 87 (1992) 161-178.
  • Downey, R.G.; Fellows, M.R.: Parameterized Computational Feasibility. In: Clote, P.; Remmel, J. (Eds.), Feasible Mathematics II, pp. 219-244, Birkhäuser, Boston, 1995.
  • Downey, R.G.; Fellows, M.R.: Parameterized Complexity. Springer-Verlag, New York, 1999.