BBMCSP 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 all top 5 Cited by 26 Authors 5 San Segundo, Pablo 4 Furini, Fabio 2 Cai, Shaowei 2 Ljubić, Ivana 2 Wang, Yiyuan 1 Artieda, Jorge 1 Buchanan, Austin 1 Chen, Jiejiang 1 Coniglio, Stefano 1 Gualandi, Stefano 1 Jiang, Hua 1 Kadivar, Mehdi 1 León, Rafael 1 Li, Chumin 1 Li, Yu 1 Lin, Jinkun 1 Liu, Yanli 1 López, Álvaro G. 1 Manyà, Felip 1 Martin, Sébastien 1 Mohammadi, Neda 1 Pardalos, Panos M. 1 Strash, Darren 1 Walteros, Jose L. 1 Yin, Minghao 1 Zhao, Yanlu all top 5 Cited in 7 Serials 4 European Journal of Operational Research 2 Computers & Operations Research 1 Artificial Intelligence 1 Operations Research 1 The Journal of Artificial Intelligence Research (JAIR) 1 INFORMS Journal on Computing 1 Transactions on Combinatorics Cited in 4 Fields 8 Operations research, mathematical programming (90-XX) 7 Combinatorics (05-XX) 3 Computer science (68-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year