罗卫东,王建新,冯启龙.最大圈分解问题的研究进展[J].计算机科学,2017,44(1):1-6, 31
最大圈分解问题的研究进展
Survey of Cycle Packing Problem
投稿时间:2015-11-17  修订日期:2016-03-18
DOI:10.11896/j.issn.1002-137X.2017.01.001
中文关键词:  最大圈分解,图论,近似算法,参数算法,不可近似性,参数复杂性
英文关键词:Cycle packing,Graph theory,Approximation algorithms,Parameterized algorithms,Inapproximability,Parameterized complexity
基金项目:本文受国家自然科学基金(61402054,4,61370172)资助
作者单位E-mail
罗卫东 中南大学信息科学与工程学院 长沙410083  
王建新 中南大学信息科学与工程学院 长沙410083  
冯启龙 中南大学信息科学与工程学院 长沙410083 lyqilong@163.com 
摘要点击次数: 2438
全文下载次数: 9026
中文摘要:
      最大圈分解问题最早由Erds和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用。主要介绍了该问题的研究现状。首先讨论了该问题在图论方面的研究进展;随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论;最后给出了该问题的进一步研究方向。
英文摘要:
      Cycle packing problem was first presented by Erds and Pósa.Since then researchers have been studying the problem in graph theory and theoretical computer science.Recently,researchers find that the problem has improtant applications in computational biology,especially for reconstruction of evolutionary trees and genomic analysis.In this paper,an introduction to the research status of this problem was given.First and foremost,some results of cycle packing problem in graph theory were discussed.Then,we analyzed and discussed approximation algorithms,parameterized algorithms,parameterized complexity and inapproximability of the problem.At last,some further research directions on this problem were given.
查看全文  查看/发表评论  下载PDF阅读器