两元指纹向量聚类问题的复杂性与改进启发式算法

• 作者: 刘培强 朱大铭 范辉 谢青松 马绍汉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 算法 复杂性 指纹向量聚类 基因表达谱 团划分
• 年，卷（期）: 2008,（3）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 500-510
• 页数: 11页
• 分类号: TP301
• 字数: 10789字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2008.00500

摘要

证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figucroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2p)减小为O(m·(n-p+1)·2P),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2p)减小为O(m·2p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱大铭	山东大学计算机科学技术学院	50	263	11.0	13.0
2	马绍汉	山东大学计算机科学技术学院	39	302	10.0	15.0
3	范辉	山东工商学院信息与电子工程学院	36	297	10.0	16.0
4	谢青松	山东工商学院信息与电子工程学院	18	80	5.0	8.0
5	刘培强	山东工商学院信息与电子工程学院	10	39	3.0	6.0