Kernelization of generic problems [Elektronische Ressource] : upper and lower bounds / vorgelegt von Stefan Kratsch

Kernelization of GenericProblemsUpper and Lower BoundsDissertationzur Erlangung des Grades desDoktors der Naturwissenschaften (Dr. rer. nat.)der Naturwissenschaftlich-Technischen Fakult atender Universit at des Saarlandesvorgelegt vonStefan KratschSaarbruc ken2010Tag des Kolloquiums: 30. August 2010Dekan:Professor Dr. Holger HermannsBerichterstatter:Professor Dr. Kurt Mehlhorn, Max-Planck-Institut fur Informatik, Saarbruc ken Dr. Hans L. Bodlaender, Utrecht University, Utrecht, the NetherlandsDr. Jiong Guo, Cluster of Excellence (MMCI), Saarbruc kenVorsitz:Professor Dr. Raimund Seidel, Saarland University, Saarbruc kenAkad. Mitarbeiter:Ben Galehouse Ph.D., Max-Planck-Institut fur Informatik, Saarbruc kenTo my parentsZusammenfassungDiese Dissertation besch aftigt sich mit der Kernelisierbarkeit von generischen Problemen,de niert durch syntaktische Beschr ankungen oder als Problemsystem. Polynomielle Ker-nelisierung ist eine Formalisierung des Konzepts der Datenreduktion fur kombinatorischschwierige Probleme. Sie erlaubt eine grundlic he Untersuchung dieses wichtigen undfundamentalen Begri s. Die Dissertation gliedert sich in zwei Hauptteile.Im ersten Teil beweisen wir, dass alle Probleme aus zwei syntaktischen Teilklassen derMenge aller konstantfaktor-approximierbaren Probleme polynomielle Kernelisierungenhaben.