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

摘要：

最大圈分解问题最早由Erd(o)s和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索.最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用.主要介绍了该问题的研究现状.首先讨论了该问题在图论方面的研究进展;随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论;最后给出了该问题的进一步研究方向.

关键词：最大圈分解、图论、近似算法、参数算法、不可近似性、参数复杂性

所属期刊栏目：44

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

资助基金：国家自然科学基金61402054,61502054,61370172

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

页数：共7页

页码：1-6,31