Algorithms for the Maximum Click Problem with Bit Parallelism

This work addresses the Maximum Clique Problem (MCP) in graphs, a well-known NP-Complete problem in graph theory and combinatorial optimization. Most state-of-the-art branch-and-bound algorithms use the gluttonous collation heuristics both to determine the branching order and to obtain upper bounds. In many cases, differences in computational environments can make comparing results less accurate. In this study, we performed a computational comparison of the MCS algorithm, presented in the unified framework for MCP by [Carmo and Züge (2012)], with two algorithms that use bit parallelism through the Bitmap Roaring structure. This structure proved to be efficient in taking advantage of the bit parallelism proposed for the most recent algorithms.