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