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

Survey of Graph Modification Problems Related to Specific Graphs

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

Graph modification problems refer to deleting or adding edges or vertices in a graph to make a graph transform to another graph with a certain property.Graph modification problems have been widely studied for many years,especially on chordal graphs,interval graphs and unit interval graphs.Chordal graphs are the most important perfect graph class and supersets of(unit)interval graphs.There are many NP-hard problems which can be solved in polynomial time on chordal graphs.Interval graphs and unit interval graphs have momentous application on computational biology.Research on graph modification problems of these graphs make a great contribution to both computer theory and applications.This survey first summarized important results for the graph modification problems on chordal graph,interval graph and unit interval graphs,then analyzed these problems,and provided some open problems to be worth studying.