计算最短公共超串的贪婪算法

• 作者: 吴绍兵 王付艳 申时凯 申浩如 管彦庆
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 最短公共超串 覆盖 算法 贪婪算法 哈密尔顿路
• 年，卷（期）: 2007,（8）
• 所属期刊栏目: 计算机软件与算法
• 页码范围: 1757-1758,1761
• 页数: 3页
• 分类号: TP301.6
• 字数: 2501字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-7024.2007.08.007

摘要

最短公共超串问题就是对给定的子串集合找到包含每个子串的可能的串.这个问题是一个NP-完全问题.目前已有一些方法对此进行了研究.通过对各子串的分析和研究,提出了一种近似于贪婪算法的求最短公共超串问题算法,该算法可应用于解决DNA片段组装和数据压缩问题.最后给出了几个实例.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	申时凯	昆明学院计算机系	17	64	4.0	7.0
2	吴绍兵	昆明学院计算机系	2	9	2.0	2.0
3	申浩如	昆明学院计算机系	8	52	4.0	7.0
4	王付艳	昆明学院计算机系	8	55	4.0	7.0
5	管彦庆	昆明学院计算机系	4	35	2.0	4.0