Monte Carlo Clique Search

vertex size

4

edge density

0.2

Combinatorica	Monte Carlo
timing = 0.000349	timing = 0.000034
clique size = 2	clique size = 2
clique = {1, 3}	clique = {1, 3}

The Mathematica package Combinatorica can find maximum cliques in graphs; however it is very slow because the MaximumClique function performs an exhaustive search. Randomization with a Monte Carlo method accelerates the process at the cost of losing the guarantee that the solution is optimal.