翻转距离星树问题的计算复杂度和近似算法

微信服务号

微信订阅号

首页 > 过刊浏览>2002年第13卷第6期 >1117-1122

翻转距离星树问题的计算复杂度和近似算法
DOI:
                        
                    
作者:
                        
                        
                    
作者单位:
作者简介:
通讯作者:
中图分类号:
基金项目:国家自然科学基金资助项目(60073042);国家教育部青年教师基金资助项目(y66053;060602);山东省中青年科学家奖励基金资助项目(01bs03)

Computational Complexity and an Approximation Algorithm for Star-Tree Phylogeny Problem with Reversal Distance

Author:

Affiliation:

Fund Project:

摘要

图/表

访问统计

参考文献

相似文献

引证文献

资源附件

文章评论

摘要:

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.

Abstract:

In this paper, the algorithms and the computational complexity of Star-Tree phylogeny problem are studied. The Star-Tree phylogeny problem is proved to be NP-complete first. Then it is proved that there is no absolute approximation algorithm for this problem. At last, a polynomial approximation algorithm of ratio 2 is presented to compute the Star-Tree phylogeny problem.

参考文献

相似文献

引证文献

引用本文

朱大铭,马绍汉,雷鹏.翻转距离星树问题的计算复杂度和近似算法.软件学报,2002,13(6):1117-1122

复制

文章指标

点击次数:
下载次数:
HTML阅读次数:
引用次数:

历史

收稿日期:2000-07-10
最后修改日期:2001-03-01
录用日期:
在线发布日期:
出版日期:

微信服务号

微信订阅号

引用本文

分享

文章指标

历史