Aktuelles
Zur Auswahl stehende Themen:
Obere Schranken
-
Faisal N. Abu-Khzam: A kernelization algorithm for d-Hitting Set (vorgestellt von Kord).
-
Stéphan Thomassé: A 4k^2 kernel for feedback vertex set (vorgestellt von Berit).
-
Jean Daligault, Stéphan Thomassé: On Finding Directed Trees with Many Leaves und
Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel
Raible, Saket Saurabh, Yngve Villanger: Kernel(s) for Problems with No
Kernel: On Out-Trees with Many Leaves
(vorgestellt von Paul).
Untere Schranken
-
Holger Dell, Dieter van Melkebeek:
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy
collapses (vorgestellt von Holger).
-
Michael Dom, Daniel Lokshtanov, Saket Saurabh: Incompressibility through Colors and IDs (vorgestellt von Holger).
Einführung
Das Oberthema im ATI-Seminar ist dieses Semester
die Kernelisierung parametrischer Probleme.
Das Seminar setzt sehr gute und zumindest in einem Bereich auch
tiefergehende Kenntnisse der theoretischen Informatik voraus.
Zeit und Raum
Freitags 9-11 im
Schrödinger Zentrum (Rudower Chaussee 26),
Raum 1'303.
Vorträge
-
22.10.2010 Vorbesprechung
-
29.10.2010 Kord Eickmeyer Grundlagen
-
19.11.2010 Holger Dell
Die Nichtkernelisierbarkeit von Problemen
(Folien)
-
26.11.2010 Holger Dell
Die Nichtkernelisierbarkeit von Vertex Cover
(Folien)
