AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (720.5 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

An Overview of Kernelization Algorithms for Graph Modification Problems

School of Information Science and Engineering, Central South University, Changsha 410083, China.
College of Mathematics and Computer Science, Key Laboratory of High Performance Computing and Stochastic Information Processing (Ministry of Education of China), Hunan Normal University, Changsha 410081, China.
Universität des Saarlandes, Campus E 1.7, D-66123 Saarbrücken, Germany.
Show Author Information

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 problemfixed-parameter tractablekernelization algorithm

References

【1】
【1】
 
 
Crossref Google Scholar
Tsinghua Science and Technology
Volume 19 Issue 4,
August 2014
Pages 346-357
DOI: 10.1109/TST.2014.6867517

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Cite this Report
Close
Close
Cite this article:
Liu Y, Wang J, Guo J. An Overview of Kernelization Algorithms for Graph Modification Problems. Tsinghua Science and Technology, 2014, 19(4): 346-357. https://doi.org/10.1109/TST.2014.6867517

1091

Views

58

Downloads

12

Crossref

N/A

Web of Science

13

Scopus

0

CSCD
Received: 09 June 2014
Accepted: 17 July 2014
Published: 30 July 2014
© The author(s) 2014