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

• 作者: 何琨 周建荣 邹晟昊
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: NP难度 大规模图 极大团枚举 贪心染色算法 增量MaxSAT推理算法
• 年，卷（期）: 2017,（12）
• 所属期刊栏目: 计算机科学与技术
• 页码范围: 1-6
• 页数: 6页
• 分类号: TP301
• 语种: 中文
• DOI: 10.13245/j.hust.171201

摘要

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BK FC算法平均时间仅为没有预处理策略的经典算法的2.2%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何琨	华中科技大学计算机科学与技术学院	31	263	10.0	16.0
5	邹晟昊	华中科技大学计算机科学与技术学院	1	2	1.0	1.0
6	周建荣	华中科技大学计算机科学与技术学院	2	2	1.0	1.0