## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### MCQ and MCR
#### 2.2.1. MCQ in Java
#### 2.3.1 MCSa in Java

In Listing 8 we present MCSa as an extension to MCQ. Method \(search\) creates an explicit colour ordering \(ColOrd\) and the \(expand\) method is called with this in line 18 (compare this to line 20 of MCQ). Method \(expand\) now takes three arguments: The growing clique \(C\), the candidate set \(P\) and the colouring order \(ColOrd\). In line 26 \(numberSort\) is called using \(ColOrd\) (compare with line 28 in MCQ) and lines 27 to 45 are essentially the same as lines 29 to 42 in MCQ with the exception that \(ColOrd\) must also be copied and updated (lines 32, 36 and 37) prior to the recursive call to \(expand\) (line 40) and then down-dated after the recursive call (line 43). Therefore, MCSa is a simple extension of MCQ and, like MCQ, has three styles of ordering. #### 2.3.2 MCSb in Java

In Listing 9 we present MCSb as an extension to MCSa: The difference between MCSb and MCSa is in \(numberSort\), with the addition of lines 10 and 20. At line 10 we compute \(delta\) as the minimum number of colour classes required to match the search bound. At line 20, if we have exceeded the number of colour classes required to exceed the search bound and a new colour class \(k\) has been opened for vertex \(v\) and we can repair the colouring such that one less colour class is used, we can decrement the number of colours used. This repair is done in the boolean method \(repair\) of lines 43 to 57. The \(repair\) method returns true if vertex \(v\) in colour class \(k\) can be recoloured into a lower colour class, false otherwise, and can be compared to [PERSON]'s Re-NUMBER procedure. We search for a colour class \(i\), where \(i<k-1\), in which there exists only one vertex in conflict with \(v\) and we call this \(w\) (line 45). The method \(getSingleConflictVariable\), lines 32 to 41, searches for such a vertex. It takes as arguments a vertex \(v\) and a colour class \(colourClass\). If \(v\) is adjacent to only one vertex in \(colourClass\) the index of that vertex is returned (line 40), where \(0\leq conflictVar<n\), otherwise a negative number is returned (line 39). The \(repair\) method then proceeds at line 46 if a single conflicting vertex \(w\) was

Figure 5: A repair scenario with colour classes i, j and k.

found, searching for a colour class \(j\)_above_\(i\) (for loop of line 47) in which there are no conflicts with \(w\). If that was found (line 48), vertex \(v\) is removed from colour class \(k\), \(w\) is removed from colour class \(i\), \(v\) is added to colour class \(i\) and \(w\) to colour class \(j\) (lines 49 to 52), and \(repair\) delivers \(true\) (line 53). Otherwise, no repair occurred (line 56). ```
1 importjava.util. *;
2
3 classMCSaextendsMCQ{
4
5 MCSa(intn,int[][]A,int[]degree,intstyle){
6 super(n,A,degree,style);
7}
8
9 voidsearch(){
10 cpuTime =System.currentTimeMillis();
11 nodes =0;
12 colourClass =newArrayList[n];
13 ArrayList<Integer>C =newArrayList<Integer>(n);
14 ArrayList<Integer>P =newArrayList<Integer>(n);
15 ArrayList<Integer>ColOrd =newArrayList<Integer>(n);
16 for(inti=0;i<n;i++)colourClass[i] =newArrayList<Integer>(n);
17 orderVertices(ColOrd);
18 expand(C,P,ColOrd);
19}
20
21 voidexpand(ArrayList<Integer>C,ArrayList<Integer>P,ArrayList<Integer>ColOrd){
22 if(timeLimit>0&&System.currentTimeMillis()-cpuTime>=timeLimit)return;
23 nodes++;
24 intm=ColOrd.size();
25 int[]colour=newint[m];
26 numberSort(C,ColOrd,P,colour);
27 for(inti=m-1;i>=0;i--){
28 intv=P.get(i);
29 if(C.size()+colour[i]<=maxSize)return;
30C.add(v);
31 ArrayList<Integer>newP =newArrayList<Integer>(i);
32 ArrayList<Integer>newColOrd =newArrayList<Integer>(i);
33 for(intj):><=i;j++){
34 intu=P.get(j);
35 if(A[|u|||]==1)newP.add(u);
36 intw=ColOrd.get(j);
37 if(A[v||w]==1)newColOrd.add(w);
38}
39 if(newP.isEmpty()&&C.size()>maxSize)saveSolution(C);
40 if(!newP.isEmpty())expand(C,newP,newColOrd);
41C.remove(C.size()-1);
42P.remove(i);
43 ColOrd.remove((Integer)v);
44}
45}
46}
47```
1 importjava.util.