主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
朱大铭,马绍汉,雷鹏.翻转距离星树问题的计算复杂度和近似算法.软件学报,2002,13(6):1117-1122
翻转距离星树问题的计算复杂度和近似算法
Computational Complexity and an Approximation Algorithm for Star-Tree Phylogeny Problem with Reversal Distance
投稿时间:2000-07-10  修订日期:2001-03-01
DOI:
中文关键词:  算法  进化树  基因组  NP-完全性  近似性能比
英文关键词:algorithm  phylogeny  genome  NP-completeness  approximation ratio
基金项目:国家自然科学基金资助项目(60073042);国家教育部青年教师基金资助项目(y66053;060602);山东省中青年科学家奖励基金资助项目(01bs03)
作者单位
朱大铭 山东大学,计算机科学技术学院,山东,济南,250100 
马绍汉 山东大学,计算机科学技术学院,山东,济南,250100 
雷鹏 山东大学,计算机科学技术学院,山东,济南,250100 
摘要点击次数: 2798
全文下载次数: 2621
中文摘要:
      讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利