An Overview of Kernelization Algorithms for Graph Modification Problems |
| |
| Authors: | Yunlong Liu ;Jianxin Wang ;Jiong Guo |
| |
| Institution: | [1]School of Information Science and Engineering, Central South University, Changsha410083, China; [2]College of Mathematics and Computer Science, Key Laboratory of High PerformanceComputing and Stochastic Information Processing (Ministryof Education of China), Hunan Normal University, Changsha410081, China; [3]Universitat des Saarlandes, Campus E 1.7,D-66123 Saarbrticken, Germany |
| |
| Abstract: | Kernelization algorithms for graph modification problems are important ingredients in parameterized computation theory. In this paper, we survey the kernelization algorithms for four types of graph modification problems, which include vertex deletion problems, edge editing problems, edge deletion problems, and edge completion problems. For each type of problem, we outline typical examples together with recent results, analyze the main techniques, and provide some suggestions for future research in this field. |
| |
| Keywords: | graph modification problem fixed-parameter tractable kernelization algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
