## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
\begin{table}
\begin{tabular}{|l|r r r r|r r|} \hline
**instance** & \multicolumn{3}{c|}{**MCSa1**} & \multicolumn{3}{c|}{**BBMC1**} & \multicolumn{1}{c|}{**MCSa1/BBMC1**} \\ \hline brock200-1 & 524,723 & 4 & (21) & 524,723 & 2 & (21) & 2.03 \\ brock400-1 & 198,359,829 & 2,888 & (27) & 198,359,829 & 1,421 & (27) & 2.03 \\ brock400-2 & 145,597,994 & 2,089 & (29) & 145,597,994 & 1,031 & (29) & 2.03 \\ brock400-3 & 120,230,513 & 1,616 & (31) & 120,230,513 & 808 & (31) & 2.00 \\ brock400-4 & 54,440,888 & 802 & (33) & 54,440,888 & 394 & (33) & 2.03 \\ brock800-4 & 640,444,536 & 12,568 & (26) & 640,444,536 & 6,908 & (26) & 1.82 \\ MANN-a27 & 38,019 & 6 & (126) & 38,019 & 1 & (126) & 4.12 \\ MANN-a45 & 2,851,572 & 3,766 & (345) & 2,851,572 & 542 & (345) & 6.94 \\ p-hat1000-1 & 176,576 & 2 & (10) & 176,576 & 1 & (10) & 1.80 \\ p-hat1000-2 & 34,473,978 & 1,401 & (46) & 34,473,978 & 720 & (46) & 1.95 \\ p-hat1500-1 & 1,184,526 & 14 & (12) & 1,184,526 & 9 & (12) & 1.52 \\ p-hat300-3 & 624,947 & 13 & (36) & 624,947 & 5 & (36) & 2.36 \\ p-hat500-2 & 114,009 & 3 & (36) & 114,009 & 1 & (36) & 2.56 \\ p-hat500-3 & 39,260,458 & 1,381 & (50) & 39,260,458 & 606 & (50) & 2.28 \\ p-hat700-2 & 750,903 & 27 & (44) & 750,903 & 12 & (44) & 2.20 \\ san1000 & 150,725 & 10 & (15) & 150,725 & 5 & (15) & 1.76 \\ san200-0.9-2 & 229,567 & 5 & (60) & 229,567 & 2 & (60) & 2.36 \\ san200-0.9-3 & 6,815,145 & 111 & (44) & 6,815,145 & 50 & (44) & 2.20 \\ san400-0.7-1 & 119,356 & 2 & (40) & 119,356 & 1 & (40) & 2.04 \\ san400-0.7-2 & 889,125 & 19 & (30) & 889,125 & 9 & (30) & 2.12 \\ san400-0.7-3 & 521,410 & 10 & (22) & 521,410 & 5 & (22) & 2.10 \\ san400-0.9-1 & 4,536,723 & 422 & (100) & 4,536,723 & 125 & (100) & 3.37 \\ san200-0.9 & 14,921,850 & 283 & (42) & 14,921,850 & 123 & (42) & 2.30 \\ san400-0.5 & 320,110 & 2 & (13) & 320,110 & 1 & (13) & 1.85 \\ san400-0.7 & 64,412,015 & 711 & (21) & 64,412,015 & 365 & (21) & 1.95 \\ \hline \end{tabular}
\end{table} 
Table 2: DIMACS _Goldilocks_ instances: MCSa1 _vs._ BBMC1, nodes, run time in seconds and clique size. ### MCQ and MCS: The Effect of Initial Ordering

What effect does the initial ordering of vertices have on performance? First, we investigate MCQ, MCSa and MCSb with our three orderings: Style 1 being non-decreasing degree, style 2 a minimum

Figure 8: The effect of style on MCQ, MCSa and MCSb. On the left \(G(100,p)\) and on the right \(G(150,p)\). Plotted is search effort in nodes against edge probability. The top two plots are for MCQ, middle plots MCSa and bottom MCSb. width ordering, style 3 non-decreasing degree tie-breaking on the accumulated degree of neighbours. At this stage, we do not consider BBMC, as it is just a BitSet encoding of MCSa. We use random problems \(G(n,p)\) with \(n\) equal to 100 and 150 with a sample size of 100. This is shown graphically in Figure 8: On the left \(G(100,p)\) and on the right \(G(150,p)\) with average nodes visited plotted against edge probability. Plots on the first row are for MCQ, middle row MCSa and bottom MCSb. For MCQ style 3 is the winner and style 2 is worst, whereas in MCSa and MCSb style 2 is always best. Why is this? In MCQ, the candidate set is ordered as the result of colouring and this order is then used in the next colouring. Therefore, MCQ gradually disrupts the initial minimum width ordering, but MCSa and MCSb do not (and neither does BBMC). The minimum width ordering (style 2) is best for MCSa, MCSb and BBMC. Note that MCQ3 _is_ [PERSON]'s MCR [15] and our experiments on \(G(n,p)\) show that MCR (MCQ3) beats MCQ (MCQ1). We now report on the 66 DIMACS instances [31], Tables 3 and 4. Table 3 gives run times in seconds. An entry of \"--\" corresponds to the CPU time limit of 14,400

\begin{table}
\begin{tabular}{|l|c c c|c c|c c|c c|c c|} \hline  & \multicolumn{2}{c|}{**MCQ**} & \multicolumn{2}{c|}{**MCSa**} & \multicolumn{2}{c|}{**MCSb**} & \multicolumn{2}{c|}{**BBMC**} \\

search terminating early. Problems that took less than a second have been excluded from the tables.