| 翻转距离星树问题的计算复杂度和近似算法 |
| |
| 引用本文： | 朱大铭,马绍汉,雷鹏.翻转距离星树问题的计算复杂度和近似算法[J].软件学报,2002,13(6):1117-1122. |
| |
| 作者姓名： | 朱大铭 马绍汉 雷鹏 |
| |
| 作者单位： | 山东大学,计算机科学技术学院,山东,济南,250100 |
| |
| 基金项目： | 国家自然科学基金资助项目(60073042);国家教育部青年教师基金资助项目(y66053;060602);山东省中青年科学家奖励基金资助项目(01bs03) |
| |
| 摘 要： | 讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.
|
| 关 键 词： | 算法 进化树 基因组 NP-完全性 近似性能比 |
| 收稿时间： | 2000/7/10 0:00:00 |
| 修稿时间： | 3/1/2001 12:00:00 AM |
Computational Complexity and an Approximation Algorithm for Star-Tree Phylogeny Problem with Reversal Distance |
| |
| ZHU Da-ming,MA Shao-han and LEI Peng.Computational Complexity and an Approximation Algorithm for Star-Tree Phylogeny Problem with Reversal Distance[J].Journal of Software,2002,13(6):1117-1122. |
| |
| Authors: | ZHU Da-ming MA Shao-han and LEI Peng |
| |
| 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. |
| |
| Keywords: | algorithm phylogeny genome NP-completeness approximation ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
