## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### MCQ and MCR
#### 2.2.1. MCQ in Java
Looking at lines 39 of Listing 3, \(|C|+|newP|\) must be greater than \(maxSize\). Since the colour of the vertex selected \(colour[i]\) was sufficient to satisfy the condition of line 30, it must be that integer vertex \(v\) (line 31) is adjacent to at least \(colour[i]\) vertices in \(P\) and thus in \(newP\), therefore the next recursive call will not immediately fail. Consequently each call to \(expand\) corresponds to an internal node in the backtrack tree. We also see again exactly what is measured as CPU time: It includes the creation of our data structures, the reordering of vertices at the top of search and all recursive calls to \(expand\) (lines 12 to 20). Why is \(colourClass\) an ArrayList\([]\) rather than an ArrayList\(<\)ArrayList\(<\)Integer\(>>\)? That would have done away with the explicit cast in line 60. When using an ArrayList\(<\)ArrayList\(<\)Integer\(>>\) Java generates an implicit cast, so nothing is gained--it is merely syntactic sugar. [PERSON]'s presentation of MCQ [12] differs from Listing 3 in that it initially colours the sorted vertices prior to calling \(expand\) and thereafter colour-sorts the new candidate set immediately before making a recursive call to \(expand\). Appendix 1 explains this in detail and investigates the effect on performance. ### Mcs

In [13] MCS is presented as two modifications to MCQ. The first modification is to use \"... an adjunct ordered set of vertices for approximate coloring\". This is an ordered list of vertices to be used in the sequential colouring, and was called \(V_{a}\). This order is static, set at the top of search. Therefore, rather than using the order in the candidate set \(P\) for colouring the vertices in \(P\), the vertices in \(P\) are coloured in the order of vertices in \(V_{a}\). The second modification is to use a repair mechanism when colouring vertices (this is called a Re-NUMBER in Figure 1 of [13]). When colouring vertices, an attempt is made to reduce the colours used by performing exchanges between vertices in different colour classes. In [13] a recolouring of a vertex \(v\) occurs when a new colour class is about to be opened for \(v\) and that colour class exceeds the search bound, _i.e._, if the number of colours can be reduced, this could result in search being cut off. In the context of colouring, I will say that vertex \(u\) and \(v\)_conflict_ if they are adjacent, and that \(v\)_conflicts_ with a colour class \(C\) if there exists a vertex \(u\in C\) that is in _conflict_ with \(v\). Assume vertex \(v\) is in colour class \(C_{k}\). If there exists a lower colour class \(C_{i}\) (\(i<k-1\)) and \(v\) conflicts with only a single vertex \(w\in C_{i}\) and there also exists a colour class \(C_{j}\), where \(i<j<k\), and \(w\) does not conflict with any vertex in \(C_{j}\), then we can place \(v\) in \(C_{i}\) and \(w\) in \(C_{j}\), freeing up colour class \(C_{k}\). This is given in Figure 1 of [13] and the procedure is named Re-NUMBER. Figure 5 illustrates this procedure. The boxes correspond to colour classes \(i\), \(j\) and \(k\) where \(i<j<k\). The circles correspond to vertices in that colour class and the red arrowed lines as conflicts between pairs of vertices. Vertex \(v\) has just been added to colour class \(k\), \(v\) conflicts only with \(w\) in colour class \(i\), and \(w\) has no conflicts in colour class \(j\). We can then move \(w\) up to colour class \(j\) and \(v\) down to colour class \(i\)Experiments were then presented in [13] comparing MCR against MCS in which MCS is always the champion. But it is not clear where the advantage of MCS comes from: Does it come from the static colour order (the \"adjunct ordered set\") or does it come from the colour repair mechanism? I now present two versions of MCS. The first, which I call MCSa, uses the static colouring order. The second, MCSb, uses the static colouring ordering _and_ the colour repair mechanism (so MCSb _is_ [PERSON]'s MCS). Consequently, we will be able to determine where the improvement in MCS comes from: Static colour ordering or colour repair.