Kernelization Techniques and Its Applications to Parameterized Computation
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    According to parameterized complexity theory, a decidable parameterized problem is fixed-parameter tractable if and only if it can be kernelized. Kernelization is the most widely applied and effective technique in the parameterized algorithm design. It is one of the hottest issues in parameterized complexity theory. This paper firstly introduces four main kernelization techniques, which are compared and analyzed with practical examples. Then it discusses how to apply these techniques to parameterized problems, such as covering problems, packing problems and cutting problems. Finally, the paper gives the future research directions about kernelization, especially the new possible kernelization technique and the kernel optimization of several FPT problems.

    Reference
    Related
    Cited by
Get Citation

李绍华,王建新,陈建二.参数计算中核心化技术及其应用.软件学报,2009,20(9):2307-2319

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:
  • Revised:February 16,2009
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063