## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
This reordering is expensive and takes place high up in the backtrack tree and is controlled by a parameter \(T_{limit}\). Varying this parameter influences the cost of the search process and \(T_{limit}\) must be tuned on an instance-by-instance basis. **2010:** [PERSON] and [PERSON] presented an early version of BBMC (BB-MCP) [27] and [PERSON] presented MCS [13]. In the same year [PERSON] and [PERSON] proposed new max-SAT encodings for maximum clique [6, 18]. **2011:** [PERSON] proposed BBMC [11] and BBMCR [10], where BBMCR includes a colour repair step. In [10] it is noted that in [13] \"... the concrete contribution of recolouring is unfortunately not made explicit.\" [PERSON]'s colour repair, \(BB\_{ReCol}\) differs from that in Listing 9 in that a _single swap_ can occur after a double swap (as in lines 49 to 52 of Listing 9). This cannot occur in Listing 9 because \(repair\) (line 43) is called only when a new colour class \(k\) is opened for vertex \(v\) (line 20); consequently \(v\) must have been adjacent to at least one vertex in each colour class less than \(k\) and therefore \(count\) (line 34) cannot be equal to zero at line 40. **2012:** [PERSON] and [PERSON] [2] reported an empirical study of 8 algorithms including those from [3] and [4] along with MCQ, MCR, MCS and MaxCliqueDyn. The claim is made that the Bron Kerbosch algorithm provides a unified framework for all the algorithms studied, although a Not Set is not used. Neither do they use pivoting as described in [16, 23, 24, 25]. All algorithms are coded in Python, therefore the study is _objective_ (the authors include none of their own algorithms) and _fair_ (all algorithms are coded by the authors and run in the same environment). BBMC is not include in the study, MCS is not broken into its constituent parts (MCSa and MCSb), and the study uses only the DIMACS benchmarks. ## 4 The Computational Study

The computational study attempts to answer the following questions. 1. Where does the improvement in MCS come from? By comparing MCQ with MCSa we can measure the contribution due to static colouring, and by comparing MCSa with MCSb we can measure the contribution due to colour repair. 2. How much benefit can be obtained from the BitSet encoding? We compare MCSa with BBMC over a variety of problems. 3. We have three possible initial orderings (styles). Is any one of them better than the others and is this algorithm independent? 4. Most papers use only random problems and the DIMACS benchmarks. What other problems might we use in our investigation? 5. Is it safe to recalibrate published results? Throughout our study we use a reference machine (named Cyprus), a machine with two Intel E5620 2.4 GHz quad-core processors with 48 GB memory, running Linux CentOS 5.3 and Java version 1.6.0_07. ### MCQ vs. MCS: Static Ordering and Colour Repair

Is MCS faster than MCQ, and if so, why? MCSa is MCQ with a static colour ordering set at the top of search, and MCSb is MCSa with the colour repair mechanism. By comparing these algorithms, we can determine if indeed MCSb is faster than MCQ and where that gain comes from--the static colouring order or the colour repair. We start our investigation with Erdos-Renyi random graphs \(G(n,p)\) where \(n\) is the number of vertices and each edge is included in the graph with probability \(p\) independent from every other edge. The first experiments are on random \(G(n,p)\), first with \(n=100\), \(0.40\leq p\leq 0.99\), \(p\) varying in steps of 0.01, sample size of 100, then with \(n=150\), \(0.50\leq p\leq 0.95\), \(p\) varying in steps of 0.05, sample size of 100, and \(n=200\), \(0.55\leq p\leq 0.95\), \(p\) varying in steps of 0.05, sample size of 100. Unless otherwise stated, all experiments are carried out on our reference machine. The algorithms MCQ, MCSa and MCSb all use \(style=1\) (_i.e._, MCQ1, MCSa1, MCSb1). Figure 6 shows on the left the average number of nodes against the edge probability and on the right the average run time in milliseconds against the edge probability, for MCQ1, MCSa1 and MCSb1.