Title of article :
An Overview of Kernelization Algorithms for Graph Modification Problems
Author/Authors :
Liu, Yunlong Hunan Normal University - Key Laboratory of High Performance Computing and Stochastic Information Processing (Ministry of Education of China), College of Mathematics and Computer Science, China , Liu, Yunlong Central South University - School of Information Science and Engineering, China , Wang, Jianxin Central South University - School of Information Science and Engineering, China , Guo, Jiong Universität des Saarlandes, 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
Journal title :
Tsinghua Science and Technology
Journal title :
Tsinghua Science and Technology
