| 最大圈分解问题的研究进展 |
| |
| 引用本文： | 罗卫东,王建新,冯启龙.最大圈分解问题的研究进展[J].计算机科学,2017,44(1):1-6, 31. |
| |
| 作者姓名： | 罗卫东 王建新 冯启龙 |
| |
| 作者单位： | 中南大学信息科学与工程学院 长沙410083,中南大学信息科学与工程学院 长沙410083,中南大学信息科学与工程学院 长沙410083 |
| |
| 基金项目： | 本文受国家自然科学基金(61402054,4,61370172)资助 |
| |
| 摘 要： | 最大圈分解问题最早由Erds和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用。主要介绍了该问题的研究现状。首先讨论了该问题在图论方面的研究进展；随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论；最后给出了该问题的进一步研究方向。
|
| 关 键 词： | 最大圈分解 图论 近似算法 参数算法 不可近似性 参数复杂性 |
| 收稿时间： | 2015/11/17 0:00:00 |
| 修稿时间： | 2016/3/18 0:00:00 |
Survey of Cycle Packing Problem |
| |
| LUO Wei-dong,WANG Jian-xin and FENG Qi-long.Survey of Cycle Packing Problem[J].Computer Science,2017,44(1):1-6, 31. |
| |
| Authors: | LUO Wei-dong WANG Jian-xin and FENG Qi-long |
| |
| Affiliation: | School of Information Science and Engineering,Central South University,Changsha 410083,China,School of Information Science and Engineering,Central South University,Changsha 410083,China and School of Information Science and Engineering,Central South University,Changsha 410083,China |
| |
| Abstract: | |
| |
| Keywords: | Cycle packing Graph theory Approximation algorithms Parameterized algorithms Inapproximability Parameterized complexity |
|
|
点击此处可从《计算机科学》下载全文 |
|
