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

• 作者: 朱大铭 雷鹏 马绍汉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 算法 进化树 基因组 NP-完全性 近似性能比
• 年，卷（期）: 2002,（6）
• 页码范围: 1117-1122
• 页数: 6页
• 分类号: TP301
• 字数: 4626字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱大铭	山东大学计算机科学技术学院	50	263	11.0	13.0
2	马绍汉	山东大学计算机科学技术学院	39	302	10.0	15.0
3	雷鹏	山东大学计算机科学技术学院	1	4	1.0	1.0