Home
Schedule
Abstract Template
Masters Attendance
Kernelisation:AnalysisOfPreprocessing

Stc
Date: 2010-03-11

Time: 11:00

Room:  [[http://www.cs.uu.nl/docs/reach/bbl.php][BBL]] [[http://www.cs.uu.nl/info/plan/bbl.php][061]]

----+++++ Speaker: Hans Bodlaender 

----+++++ Title: Kernelisation: Analysis of Preprocessing 

----+++++  Abstract

A common approach when solving computationally hard (e.g., NP-complete) problems in practice is to start
with a preprocessing phase, where the input is transformed to an equivalent, and usually smaller input. E.g., for
many graph problems, preprocessing where vertices of degree zero or one are removed, is possible. With help of techniques from the area of fixed parameter tractability, we can analyse how effective such preprocessing can be, i.e., give bounds on resulting instances after polynomial time preprocessing. This talk surveys several recent results from this area of kernelisation, including kernels for some specific problems, and lower bound techniques.