Home
Schedule
Abstract Template
Masters Attendance
Center
Home
Courses
People
Projects
Page
Edit Page
Rename Page
Attach File
Printable
Wiki Source
More ...
Web
Recent Changes
Notify Service
News
Page Index
Search
More ...
Wiki
About TWiki
Text Formatting
Registration
Change Password
Reset Password
Users
Groups
Log In
or
Register
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.