目标序列部分确定的翻转距离星树问题

• 作者: 朱大铭 栾峻峰 马绍汉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 算法 计算复杂性 进化树 基因组 翻转距离
• 年，卷（期）: 2003,（2）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 183-189
• 页数: 7页
• 分类号: TP301
• 字数: 5417字
• 语种: 中文

摘要

讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时,若目标序列符号顺序固定,且有部分符号方向给定,则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP-难解问题.同时,还给出了该问题的多项式时间近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱大铭	山东大学计算机科学与技术学院	50	263	11.0	13.0
2	马绍汉	山东大学计算机科学与技术学院	39	302	10.0	15.0
3	栾峻峰	山东大学计算机科学与技术学院	12	19	3.0	3.0