A new exact maximum clique algorithm for large and massive sparse graphs. (February 2016)

• Record Type: Journal Article
• Authors: San Segundo, Pablo; Lopez, Alvaro; Pardalos, Panos M.
• Is Part Of: Computers & operations research. Volume 66(2016)
• Page Start: 81
• Page End: 94
• Publication Date: 2016-02
• Subjects: Branch and bound -- Bitstring -- Massive -- Sparse -- Maximum clique; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.07.013
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: New state-of-the-art exact maximum bit-parallel clique algorithm tailored for massive graphs. New sparse bit parallel encoding. Improved preprocessing to reduce the problem´s scale.