论文部分内容阅读
证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard，并给出Figueroa等人指纹向量聚类启发式算法的改进算法．主要改进了算法的实现方法．以链表存储相容顶点集合，并以逐位扫描指纹向量的方法产生相容点集链表，可将产生相容点集的时间复杂性由O（m·n·2^p）减小为O（m·（n-p＋1）·2^p），可使划分一个唯一极大团或最大团的时间复杂性由O（m·p·2^p）减小为O（m·2^p）．实际测试显示，改进算法的空间复杂性平均减少为原算法