BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

A brief introduction to kernelization Kratsch, Stefan


Kernelization is a notion from parameterized complexity that captures the concept of efficient preprocessing for NP-hard problems. A kernelization is a polynomial-time algorithm that given an instance (x; k) with parameter k will return an equivalent instance of size bounded only in terms of k. In particular, we are interested in polynomial kernels where the bound depends polynomially on k. The talk will give an introduction to core concepts from kernelization. Where appropriate, relations to approximability of the considered problems will be discussed

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International