特殊图的图修正问题研究综述

摘要：

图修正问题是指在一个图中进行删除点、删除边或加边操作,使这个图转变成另一个具有某种特殊性质的图.图修正问题一直被广泛研究,尤其对弦图、区间图以及单位区间图的图修正问题的研究更是如此.弦图是完美图中最重要的一类图,也是(单位)区间图的父类图,很多经典的NP难问题在弦图上都是多项式可解的.区间图以及单位区间图在生物计算上有着广泛的应用.对这几类图的图修正问题的研究对计算机理论和实践有很大的贡献.首先介绍并总结了关于弦图、区间图以及单位区间图的图修正问题的重要算法和技术,然后对这些问题的研究现状进行分析,并提出了今后研究中值得关注的问题.

关键词：图修正问题、弦图、区间图、单位区间图

所属期刊栏目：45

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目61472449

在线出版日期：2018-04-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：9-15