## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
Fortunately we are moving into a new era where code is being made publicly available (examples here are [PERSON]'s Cliquer and [PERSON]'s MaxCliqueDyn) via the web. Hopefully this will grow and allow Computer Scientist to be better able to perform reproducible empirical studies. [PERSON] [13] presented MCS as an improvement on MCR brought about via two modifications: (1) a static colour ordering and (2) a colour repair step. Our study has shown that modification (1) improves performance and (2) degrades performance, _i.e._, MCSa is better than MCSb. \begin{table}
\begin{tabular}{|c|c c|c c|c c|c c|c c|} \hline  & \multicolumn{4}{c|}{**Ciquer**} & \multicolumn{4}{c|}{**dfmax**} \\
**instance** & \multicolumn{2}{c|}{**Fais**} & \multicolumn{2}{c|}{**Daleview**} & \multicolumn{2}{c|}{**Cyprus**} & \multicolumn{2}{c|}{**Fais**} & \multicolumn{2}{c|}{**Daaleview**} & \multicolumn{2}{c|}{**Cyprus**} \\ \hline brock200-1 & 0.66 & (9,760) & 0.43 & (18,710) & 1.00 & (6,490) & 0.39 & (25,150) & 0.42 & (23,020) & 1.00 & (9,730) \\ brock200-4 & 0.64 & (690) & 0.47 & (1,190) & 1.00 & (440) & 0.41 & (1,510) & 0.46 & (1,360) & 1.00 & (620) \\ p-hat1000-1 & 0.62 & (1,750) & 0.36 & (3,020) & 1.00 & (1,090) & 0.41 & (1,680) & 0.45 & (1,540) & 1.00 & (690) \\ p-hat700-1 & 0.67 & (150) & 0.37 & (270) & 1.00 & (100) & — & — & — & — & — & — \\ san1000 & 0.75 & (120) & 0.30 & (300) & 1.00 & (90) & — & — & — & — & — & — \\ san200-0.7-1 & 0.48 & (1,750) & 0.20 & (4,220) & 1.00 & (840) & — & — & — & — & — \\ san200-0.9-2 & 0.61 & (18,850) & 0.21 & (53,970) & 1.00 & (11,530) & — & — & — & — & — & — \\ san400-0.7-3 & 0.62 & (6,800) & 0.26 & (16,100) & 1.00 & (4,230) & — & — & — & — & — \\ san200-0.7 & 0.65 & (2,940) & 0.36 & (5,270) & 1.00 & (1,900) & 0.40 & (5,240) & 0.44 & (4,770) & 1.00 & (2,080) \\ san400-0.5 & 0.62 & (1,490) & 0.38 & (2,420) & 1.00 & (930) & 0.41 & (3,550) & 0.47 & (3,080) & 1.00 & (1,460) \\ \hline ratio (total) & 0.62 & (44,300) & 0.26 & (105,470) & 1.00 & (27,640) & 0.39 & (37,130) & 0.43 & (33,770) & 1.00 & (14,580) \\ \hline \end{tabular}
\end{table} 
Table 9: Calibration experiments for Cliquer and dfmax using 3 machines. BBMC is algorithm MCSa with sets represented as bit strings, _i.e._, BitSet is used rather than ArrayList. Experiments on the reference machine showed a speedup typically of a factor of 2. The three styles of ordering were investigated. The orderings were quickly disrupted by MCQ, but in the other algorithms minimum width ordering was the best in random problems, whereas in the DIMACS instances there was no clear winner. New benchmark problems (_i.e._, problems rarely investigated by the maximum clique community) were investigated such as BHOSLIB, k-regular and small-world graphs. Motivation for this study was partly to compare algorithms but also to explore these problems to determine if and when they are hard. Finally, we demonstrated that the standard procedure for calibrating machines and rescaling results is unsafe, and that running our own code on different machines can lead to different relative algorithmic performance. This is disturbing. First, it suggests that to perform a fair and reliable empirical study we should not rescale others' results: We must either code up the algorithms ourselves, as done here and also by [PERSON] and [PERSON] [2], or download and run code on our machines. Secondly, we should run our experiments on different machines. All the codes used in this study are available online [34] along with instructions on how to run the code, the DIMACS instances, random problem generator and runtime results.