swMATH ID: 17718
Software Authors: San Segundo, Pablo; Lopez, Alvaro; Pardalos, Panos M.
Description: A new exact maximum clique algorithm for large and massive sparse graphs. 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.
Homepage: http://www.sciencedirect.com/science/article/pii/S0305054815001884
Keywords: branch and bound; bitstring; massive; sparse; maximum clique
Related Software: BBMCL; DIMACS; MaxCliqueDyn; GitHub; SCCWalk; Algorithm 457; BITSCAN; COL; MINION; CPLEX; KONECT; SURF; SIFT; MCODE; BBMCW; OEIS; igraph; CSDP; Benchmarks for Optimization Software; SCIP
Cited in: 11 Publications

Citations by Year