You are here:
(10 Mar 2011,
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]] ----+++++ 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.
ore topic actions
Topic revision: r1 - 10 Mar 2011,
Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UUCS?