首页> 中文期刊> 《软件学报》 >翻转距离星树问题的计算复杂度和近似算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《软件学报》 |2002年第6期|1117-1122|共6页
作者
朱大铭; 马绍汉; 雷鹏;
展开▼
作者单位

山东大学;

计算机科学技术学院;

山东;

济南;

250100;

山东大学;

计算机科学技术学院;

山东;

济南;

250100;

山东大学;

计算机科学技术学院;

山东;

济南;

250100;

展开▼
原文格式 PDF
正文语种 chi
中图分类理论、方法;
关键词
算法; 进化树; 基因组; NP-完全性; 近似性能比;

相似文献

中文文献
外文文献
专利

1. 目标序列部分确定的翻转距离星树问题 [J] . 栾峻峰 ,朱大铭 ,马绍汉 . 软件学报 . 2003,第002期
2. 实例序列条数为常数9的翻转距离星树问题 [J] . 栾峻峰 ,朱大铭 ,马绍汉 . 计算机研究与发展 . 2003,第008期
3. 一般设施定位问题计算复杂度和近似算法研究 [J] . 潘锐 ,朱大铭 ,马绍汉 . 计算机研究与发展 . 2007,第005期
4. 求解Hamming距离下的最短路改进问题的一个近似算法 [J] . 张斌武 ,王勤 ,余维燕 . 兰州理工大学学报 . 2008,第004期
5. 边着色图上最大弱适当树问题近似算法 [J] . 金世豪 ,陈光亭 ,陈永 . 杭州电子科技大学学报 . 2021,第004期
6. 目标序列符号顺序固定的翻转距离星树问题 [C] . 栾峻峰 ,朱大铭 ,马绍汉 . 2001年全国理论计算机科学学术会议 . 2001
7. K-Median问题的近似计算复杂度与局部搜索近似算法分析 [A] . 潘锐 . 2004

获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

客服微信
服务号