最大圈分解问题的研究进展

发布时间：2018-11-16 15:06

【摘要】：最大圈分解问题最早由Erd銉s和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用。主要介绍了该问题的研究现状。首先讨论了该问题在图论方面的研究进展;随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论;最后给出了该问题的进一步研究方向。
[Abstract]:The problem of maximum cycle decomposition was first proposed by Erd s and P 贸 sa, and then widely explored by researchers in the field of graph theory and theoretical computer science. Recent studies have found that this problem has important applications in computational biology, especially in the research of constructing evolutionary trees and analyzing genomes. This paper mainly introduces the research status of this problem. This paper first discusses the research progress of the problem in graph theory, then analyzes and discusses the approximate algorithm of the problem, parameter complexity and inapproximation, and finally gives the further research direction of the problem.
【作者单位】： 中南大学信息科学与工程学院;
【基金】：国家自然科学基金(61402054,61502054,61370172)资助
【分类号】：TP301.6;O157.5

【相似文献】

相关期刊论文 前10条

1 魏麒;蒋义伟;;一类两阶段杂交流水作业的近似算法(英文)[J];软件学报;2012年05期

2 刘振宏;组合最优化问题的近似算法[J];数学的实践与认识;1983年03期

3 马绍汉;一类限制树问题的复杂性及其近似算法[J];山东大学学报(自然科学版);1984年01期

4 杨延龄,戚文发;关于最优备件问题的近似算法的研究[J];工程数学学报;1989年01期

5 杜林古;;带风向投递员问题的一个多项式1—近似算法[J];山东纺织工学院学报;1992年01期

6 苏纯洁;带服务器的三台平行机排序问题的复杂性和近似算法[J];应用数学学报;2003年03期

7 刘光聪;朱大铭;姜海涛;;有向基因组反转和转位排序最小权重问题的1.5k近似算法[J];小型微型计算机系统;2010年07期

8 何勇;带核集分划问题的一个线性(1/7)-近似算法[J];高校应用数学学报A辑(中文版);1997年04期

9 季敏,何勇;带核集分划问题的一个改进近似算法[J];系统工程理论与实践;2003年12期

10 何晓琼;陈冲;李荣珩;;工厂地址集中的k-种产品选址问题的近似算法[J];计算机工程与应用;2010年08期

相关会议论文 前9条

1 刘声田;朱大铭;;基因序列翻转排序的一种近似算法[A];山东省计算机学会2005年信息技术与信息化研讨会论文集（一）[C];2005年

2 梅生伟;洪奕光;秦化淑;翁绍鹏;;非线性H_∞控制的粘性解及其近似算法[A];1996年中国控制会议论文集[C];1996年

3 田世俊;李建;朱洪;;多需求目标的UFL问题及其近似算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 梁国宏;郭云霞;郑明发;;最大化下模函数的近似算法及其性能保证[A];第十届中国不确定系统年会、第十四届中国青年信息与管理学者大会论文集[C];2012年

5 保利勇;赵东风;丁洪伟;;双服务器异步控制策略轮询系统性能的近似算法分析[A];2009年中国高校通信类院系学术研讨会论文集[C];2009年

6 任建峰;张玉忠;孙国;;一种新的柔性车间排序问题[A];中国企业运筹学学术交流大会论文集[C];2005年

7 李灏;张春路;丁国良;;对多层墙体反应系数的一种近似算法的讨论[A];上海市制冷学会一九九七年学术年会论文集[C];1997年

8 李灏;张春路;丁国良;;对多层墙体反应系数的一种近似算法的讨论[A];全国暖通空调制冷1998年学术年会论文集（2）[C];1998年

9 周露;吴瑶华;黄文虎;闻新;;一种推广卡尔曼滤波的近似算法[A];1995中国控制与决策学术年会论文集[C];1995年

相关重要报纸文章 前1条

1 PALADIN;近似算法[N];电脑报;2003年

相关博士学位论文 前5条

1 杨朝霞;超图嵌入圈问题的近似算法[D];山东大学;2010年

2 潘锐;设施选址与K-中间点问题的复杂性与近似算法[D];山东大学;2007年

3 陈仕平;若干组合优化问题的近似算法设计与分析[D];浙江大学;2002年

4 柳楠;基因组片段填充问题的算法研究[D];山东大学;2013年

5 姜海涛;基因组比较算法研究[D];山东大学;2011年

相关硕士学位论文 前10条

1 陈崇琛;多色点集直线划分的复杂性及其近似算法[D];复旦大学;2014年

2 王敏;基于图特征的介度中心近似算法研究[D];曲阜师范大学;2015年

3 张亚平;最小赋权连通k-子图覆盖问题的近似算法[D];新疆大学;2015年

4 张永俊;广义非线性分式规划问题的近似算法[D];河南师范大学;2015年

5 朱婷婷;具有不同释放时间的单机重新排序问题的近似算法[D];兰州大学;2016年

6 王克红;均匀限制NP-完备间题及其近似算法设计[D];云南大学;2016年

7 肖文英;限制版本瓶颈斯坦纳树问题算法研究[D];中南民族大学;2015年

8 李彦杰;连通控制吸收集的近似算法[D];新疆大学;2013年

9 张峰;漫射光化通量的二流四流混合近似算法求解[D];中国气象科学研究院;2010年

10 刘海;非光滑问题的三次近似算法[D];北京工业大学;2014年

，

本文编号：2335852