柯玉平,王建新.特殊图的图修正问题研究综述[J].计算机科学,2018,45(3):9-15
特殊图的图修正问题研究综述
Survey of Graph Modification Problems Related to Specific Graphs
投稿时间:2017-01-09  修订日期:2017-04-19
DOI:10.11896/j.issn.1002-137X.2018.03.002
中文关键词:  图修正问题,弦图,区间图,单位区间图
英文关键词:Graph modification,Chordal graph,Interval graph,Unit interval graph
基金项目:本文受国家自然科学基金项目(61472449)资助
作者单位E-mail
柯玉平 中南大学信息科学与工程学院 长沙410083 karepy2014@csu.edu.cn 
王建新 中南大学信息科学与工程学院 长沙410083 jxwang@mail.csu.edu.cn 
摘要点击次数: 705
全文下载次数: 396
中文摘要:
      图修正问题是指在一个图中进行删除点、删除边或加边操作,使这个图转变成另一个具有某种特殊性质的图。图修正问题一直被广泛研究,尤其对弦图、区间图以及单位区间图的图修正问题的研究更是如此。弦图是完美图中最重要的一类图,也是(单位)区间图的父类图,很多经典的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 polynomialtime 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.
查看全文  查看/发表评论  下载PDF阅读器