|
|||||
|
|
| 华中科技大学学报(自然科学版) 2017年 第45卷 总目次 | |
| 作者单位： | ;1.华中科技大学计算机科学与技术学院;2.深圳华中科技大学研究院 |
| 摘 要： | 将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%. |
| 关 键 词： | NP难度 大规模图 极大团枚举 贪心染色算法 增量MaxSAT推理算法 |
Enumerating maximal cliques in large sparse graphs |
|
| Abstract: | <正>~~ |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ | |
