## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
The results are shown as three dimensional plots in Figure 10: The graph above is average search effort and below average maximum clique size. Looking at the graph above: When \(p=0.0\) problems are easy; as \(p\) increases and randomness is introduced, the problems quickly get hard, but as \(p\) continues to increase the graphs tend to become predominantly random and behave more like large sparse random graphs and get easier. We also see that as neighbourhood size \(k\) increases, the problems get harder. We can compare the \(SW(1000,100,p)\) to the graphs \(G(1000,0.2)\) in Table 6: \(G(1000,0.2)\) took on average 39,478 nodes whereas \(SW(1000,100,0.01)\) took 709,347 nodes, \(SW(1000,100,0.08)\) took 2,702,199 nodes and \(SW(1000,100,0.25)\) 354,430 nodes. Clearly small-world instances are relatively hard. Looking at the graph below (average maximum clique size), we see that as rewiring probability \(p\) increases maximum cliques size decreases, and as \(k\) increases so too does maximum clique size. ### Calibration of Results

To compare computational results across publications a standard C program, dfmax, is compiled and run against a set of benchmarks. These run times are then used as a conversion factor, and the results are then taken from one publication, scaled accordingly, and then included in another publication. Recent examples of this are [7] including rescaled results from [33]; [9] including rescaled results from [7], [14] and [4]; [15] including rescaled results from [7] and [33]; [11] including rescaled results from [5]; [10] including rescaled results from [11]; [6] including rescaled results from [9,15]. Is this procedure safe? To test this we take two additional machines, Fais and Daleview, and calibrate them with respect to our reference machine Cyprus. We then run experiments on each machine using the Java implementations of the algorithms implemented here against some of the DIMACS benchmarks. These results are then rescaled. If the rescaling gives substantially different results from those on the reference machine, this would suggest that this technique is not safe. Table 7 gives a \"Rosetta Stone\" for the three machines used in this study. The standard program dfmax [37] was compiled using gcc and the -O2 compiler option on each machine and then run on the benchmarks r* on each machine. Run times in seconds are tabulated for the five benchmark instances, each machine's /proc/cpuinfo is given and a conversion factor relative to the reference machine Cyprus is then computed in the same manner as that reported in [11] (\"... the first two graphs from the benchmark were removed (user time was considered too small) and the rest of the times averaged...\"). Therefore when rescaling the run times from Fais, we multiply the actual run time by 0.41 and for Daleview by 0.50. Table 8 shows the results of the calibration experiments. Tabulated are a subset of DIMACS instances that took more than 1 s and less than 2 h to solve using MCSa1 on our second slowest machine (Fais). \begin{table}
\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|} \hline
**machine** & **r100.5** & **r200.5** & **r300.5** & **r400.5** & **r500.5** & **Intel(R)** & **GHz** & **cache** & **Java** & **scaling factor** \\ \hline Cyprus & 0.0 & 0.02 & 0.24 & 1.49 & 5.58 & Xeon(R) E5620 & 2.40 & 12,288 KB & 1.6.0/0.7 & 1 \\ \hline Fais & 0.0 & 0.08 & 0.58 & 3.56 & 13.56 & Xeon(TM) CPU & 2.40 & 512 KB & 1.5.0/0.6 & 0.41 \\ \hline Daleview & 0.0 & 0.09 & 0.53 & 3.00 & 10.95 & Atom(TM) N280 & 1.66 & 512 KB & 1.6.0/1.8 & 0.50 \\ \hline \end{tabular}
\end{table} 
Table 7: Conversion factors using dfmax on three machines: Cyprus, Fais and Daleview. Run times are tabulated in milliseconds (in brackets) and the actual ratio of Cyprus-time over Fais-time (expected to be 0.41) is given as well as Cyprus-time over Daleview-time (expected to be 0.50) for each data point. Two algorithms are used, MCSa1 and BBMC1. The last row of Table 8 gives the relative performance ratios computed using the sum of the run times in the table.