## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Mc
#### 2.1.1 MC in Java  
Listing 1 can be compared with Algorithm 1 in [4]. The constructor, lines 14 to 22, takes three arguments: \(n\) the number of vertices in the graph, \(A\) the adjacency matrix where \(A[i][j]\) equals 1 if and only if vertex \(i\) is adjacent to vertex \(j\), and \(degree\) where \(degree[i]\) is the number of vertices adjacent to vertex \(i\) (and is the sum of \(A[i]\)). The variables \(nodes\) and \(cpuTime\) are used as measures of search performance, \(timeLimit\) is a bound on the run-time, \(maxSize\) is the size of the largest clique found so far, \(style\) is used as a flag to customise the algorithm with respect to ordering of vertices (and is not used till we get to MCQ), and the array \(solution\) is the largest clique found such that \(solution[i]\) is equal to 1 if and only if vertex \(i\) is in the largest clique found.  
The method \(search()\) finds a largest clique or terminates when having exceeded the allocated \(timeLimit\). Two sets are produced: The _candidate set_\(P\) and the _current clique_\(C\). Vertices from \(P\) may be selected and added to the growing clique \(C\). Initially all vertices are added to \(P\) and \(C\) is empty (lines 27 to 29). The sets \(P\) and \(C\) are represented using Java's ArrayList, a resizable-array implementation of the List interface. Adding an item is an \(O(1)\) operation but removing an arbitrary item is of \(O(n)\) cost. This might appear to be a damning indictment of this simple data structure, but as we will see, it is the cost we pay if we want to maintain order in \(P\), and in many cases we can work around this to enjoy \(O(1)\) performance.  
The search is performed in method \(expand\). In line 34, a test is performed to determine if the CPU time limit has been exceeded, and if so search terminates. Otherwise we increment the number of nodes, _i.e._, a count of the size of the backtrack search tree explored. The method then iterates over the vertices in \(P\) (line 36), starting with the last vertex in \(P\) down to the first vertex in \(P\). This form of iteration over the ArrayList, getting entries with a specific index, is necessary when entries are deleted (line 45) as part of that iteration. A vertex \(v\) is selected from \(P\) (line 38), added to \(C\) (line 39), and a new candidate set \(newP\) is then created (line 40) where \(newP\) is the set of vertices in \(P\) that are adjacent to vertex \(v\) (line 41). Consequently all vertices in \(newP\) are adjacent to all vertices in \(C\) and all pairs of vertices in \(C\) are adjacent (_i.e._, \(C\) is a clique). If \(newP\) is empty \(C\) is maximal and if it is the largest clique found it is saved (line 42). If \(newP\) is not empty then \(C\) is not maximal and search can proceed via a recursive call to \(expand\) (line 43). On returning from the recursive call \(v\) is removed from \(P\) and from \(C\) (lines 44 and 45).  
There is one \"trick\" in \(expand\) and that is at line 37: If the combined size of the current clique and the candidate set cannot unseat the champion, this branch of the backtrack tree can be abandoned. This is the simplest upper bound cut-off and corresponds to line 3 from Algorithm 1 in [4]. The method \(saveSolution\) saves off the current maximal clique and records its size.