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

Enumerating maximal cliques in large sparse graphs

作　　者：何琨[1,2] 邹晟昊 周建荣 He Kun;Zou Shenghao;Zhou Jianrong(School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China;Research Institute of Huazhong University of Science and Technology in Shenzhen, Shenzhen 518057, Guangdong China)

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074 [2]深圳华中科技大学研究院,广东深圳518057

出　　处：《华中科技大学学报（自然科学版）》2017年第12期1-6,共6页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61772219;61472147;61602196);深圳市科技计划资助项目(JCYJ20170307154749425)

摘　　要：将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.Several maximum clique algorithms were adapted to the maximal clique problem,and two algorithms were proposed for the maximal clique enumeration problem with the minimum clique size requirement.By iteratively removing nodes and edges that are clearly not included in the desired maximal cliques,several preprocessing strategies were designed to significantly reduce the scale of the searching space.Combining the preprocessing strategy which is best empirically,the greedy graph coloring algorithm and the MaxSAT reasoning algorithm for maximum clique problem were adopted in order to solve the maximal clique enumeration problem,and a Bron-Kerbosch with filtering and coloring（BKFC）algorithm and a Bron-Kerbosch with filtering and MaxSAT（BKFS）algorithm were proposed.For small scale graphs,BKFS takes only 2.2% time cost of the traditional algorithm which does not use the preprocessing strategy.And the traditional algorithm cannot work on large graphs.Even after adding preprocessing on the traditional algorithm,BKFS only takes 68.8%time cost of the improved traditional algorithm.

关 键 词：NP难度 大规模图 极大团枚举 贪心染色算法 增量MaxSAT推理算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]