A parallel maximum clique algorithm for large and massive sparse graphs

作者：San Segundo Pablo^*; Lopez Alvaro; Artieda Jorge; Pardalos Panos M

来源：Optimization Letters, 2017, 11(2): 343-358.

DOI：10.1007/s11590-016-1019-3

• Massive
• Bitstring
• Branch-and-bound
• Maximum clique
• Parallel Combinatorial optimization

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.

• 出版日期2017-2