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.
Keywords for this software
References in zbMATH (referenced in 9 articles )
Showing results 1 to 9 of 9.
- Cai, Shaowei; Lin, Jinkun; Wang, Yiyuan; Strash, Darren: A semi-exact algorithm for quickly computing a maximum weight clique in large sparse graphs (2021)
- Furini, Fabio; Ljubić, Ivana; San Segundo, Pablo; Zhao, Yanlu: A branch-and-cut algorithm for the edge interdiction clique problem (2021)
- Mohammadi, Neda; Kadivar, Mehdi: A local core number based algorithm for the maximum clique problem (2021)
- Walteros, Jose L.; Buchanan, Austin: Why is maximum clique often easy in practice? (2020)
- Wang, Yiyuan; Cai, Shaowei; Chen, Jiejiang; Yin, Minghao: SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem (2020)
- Furini, Fabio; Ljubić, Ivana; Martin, Sébastien; San Segundo, Pablo: The maximum clique interdiction problem (2019)
- San Segundo, Pablo; Furini, Fabio; Artieda, Jorge: A new branch-and-bound algorithm for the maximum weighted clique problem (2019)
- Li, Chu-Min; Liu, Yanli; Jiang, Hua; Manyà, Felip; Li, Yu: A new upper bound for the maximum weight clique problem (2018)
- San Segundo, Pablo; Lopez, Alvaro; Pardalos, Panos M.: A new exact maximum clique algorithm for large and massive sparse graphs (2016)