A new exact maximum clique algorithm for large and massive sparse graphs

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

来源：Computers & Operations Research, 2016, 66: 81-94.

DOI：10.1016/j.cor.2015.07.013

• Branch and bound
• Bitstring
• Massive
• Sparse
• Maximum clique

This paper describes a new very efficient branch-and-bound exact maximum clique algorithm BBMCSP, designed for large and massive sparse graphs which appear frequently in real life problems from different fields.
State-of-the-art exact maximum clique algorithms encode the adjacency matrix in full but when dealing with sparse graphs some form of compression is required. The new algorithm is based on a leading bit-parallel non-sparse solver but employs a novel sparse encoding for the adjacency matrix. Moreover, it also improves on recent optimizations proposed in literature for the sparse case such as core-based bounds.
Reported results show that it is several orders of magnitude better than state-of-the-art. Moreover, a number of real networks with many millions of nodes are solved in a few seconds.

• 出版日期2016-2