zbMATH — the first resource for mathematics

Kernelization: new upper and lower bound techniques. (English) Zbl 1273.68158
Chen, Jianer (ed.) et al., Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10–11, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-11268-3/pbk). Lecture Notes in Computer Science 5917, 17-37 (2009).
Summary: In this survey, we look at kernelization: algorithms that transform in polynomial time an input to a problem to an equivalent input, whose size is bounded by a function of a parameter. Several results of recent research on kernelization are mentioned. This survey looks at some recent results where a general technique shows the existence of kernelization algorithms for large classes of problems, in particular for planar graphs and generalizations of planar graphs, and recent lower bound techniques that give evidence that certain types of kernelization algorithms do not exist.
For the entire collection see [Zbl 1178.68005].

68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
Full Text: DOI