parameterized computation, kernelization, parameterized algorithm, NP-hard
Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.
Tsinghua University Press
Qilong Feng, Qian Zhou, Wenjun Li et al. Kernelization in Parameterized Computation: A Survey. Tsinghua Science and Technology 2014, 19(04): 338-345.