  Finding the clique of maximum cardinality in an arbitrary graph is an NP-Hard
problem that has many applications, which has motivated studies to solve it
exactly despite its difficulty. The great majority of algorithms proposed in
the literature are based on the Branch and Bound method. In this paper, we
propose an exact algorithm for the maximum clique problem based on the Russian
Dolls Search method. When compared to Branch and Bound, the main difference of
the Russian Dolls method is that the nodes of its search tree correspond to
decision subproblems, instead of the optimization subproblems of the Branch and
Bound method. In comparison to a first implementation of this Russian Dolls
method from the literature, several improvements are presented. Some of them
are adaptations of techniques already employed successfully in Branch and Bound
algorithms, like the use of approximate coloring for pruning purposes and
bit-parallel operations. Two different coloring heuristics are tested: the
standard greedy and the greedy with recoloring. Other improvements are directly
related to the Russian Dolls scheme: the adoption of recursive calls where each
subproblem (doll) is solved itself via the same principles than the Russian
Dolls Search and the application of an elimination rule allowing not to
generate a significant number of dolls. Results of computational experiments
show that the algorithm outperforms the best exact combinatorial algorithms in
the literature for the great majority of the dense graphs tested, being more
than twice faster in several cases.
