大规模稀疏图的极大团枚举算法

发布时间：2018-04-22 17:34

本文选题：NP难度 + 大规模图　；参考：《华中科技大学学报(自然科学版)》2017年12期

【摘要】：将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.
[Abstract]:The maximum cluster solving algorithm is integrated into the maximum cluster enumeration algorithm. Two maximum cluster enumeration algorithms with maximum clique lower bound and various preprocessing and filtering strategies are proposed. By iteration, some points and edges that can not be included in the maximal cluster are deleted. Makes the search space greatly reduced. In search strategy, greedy coloring algorithm, incremental MaxSAT reasoning algorithm and maximal cluster enumeration algorithm are combined with the best selection strategy. A color-key point fusion algorithm, BKFC(Bron-Kerbosch with filtering and coloring, and an enumeration algorithm based on incremental MaxSAT reasoning, BKFS(Bron-Kerbosch with filtering and MaxSAT, are proposed. The results show that the average time of BKFC algorithm is only 68.8% of that of the improved classical algorithm with preprocessing on many large examples, because the classical algorithm can not run on large scale examples. In the small data test, the average time of BKFC algorithm is only 2.2 of that of the classical algorithm without preprocessing strategy.
【作者单位】：华中科技大学计算机科学与技术学院;深圳华中科技大学研究院;
【基金】：国家自然科学基金资助项目(61772219,61472147,61602196) 深圳市科技计划资助项目(JCYJ20170307154749425)
【分类号】：O157.5;TP301.6

【相似文献】