A parallel maximum clique algorithm for large and massive sparse graphs

详细信息    查看全文

• 作者：Pablo San Segundo ; Alvaro Lopez ; Jorge Artieda ; Panos M. Pardalos
• 关键词：Massive ; Bitstring ; Branch ; and ; bound ; Maximum clique ; Parallel ; Combinatorial optimization
• 刊名：Optimization Letters
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：11
• 期：2
• 页码：343-358
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Optimization; Operation Research/Decision Theory; Computational Intelligence; Numerical and Computational Physics, Simulation;
• 出版者：Springer Berlin Heidelberg
• ISSN：1862-4480
• 卷排序：11

文摘

This paper describes BBMCPara, a new parallel exact maximum clique algorithm tailored for large and massive sparse graphs. The paper first presents a sequential algorithm BBMCSP, which builds on ideas from a leading bit-parallel published algorithm for middle-size graphs. It employs heavy pre-processing and a new sparse bitset encoding to outperform other state-of-the-art algorithms by up to several orders of magnitude over a set of real networks. BBMCPara parallelizes BBMCSP by splitting according to a preprocessing step of the latter. On a 20-core computer, it averages speedups close to an order of magnitude over real graphs of up to 3 million vertices. According to the reported results, BBMCPara appears to be the current fastest algorithm for large and massive real networks to the best of our knowledge.