Kernelization in Parameterized Computation: A Survey |
| |
Authors: | Qilong Feng Qian Zhou Wenjun Li Jianxin Wang |
| |
Institution: | the School of Information Science and Engineering,Central South University, Changsha 410083, China |
| |
Abstract: | 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. |
| |
Keywords: | parameterized computation kernelization parameterized algorithm NP-hard |
本文献已被 CNKI 维普 等数据库收录! |
|