## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
Their algorithm is similar to MC (Listing 1) but sorts the candidate set \(P\) using current degree in each call to \(expand\). **1992:** In [8] [PERSON] and [PERSON] present a zero-one encoding of the problem where a vertex \(v\) is represented by a variable \(x_{v}\) that takes the value 1 if search decides that \(v\) is in the clique and 0 if it is rejected. Pruning takes place via the constraint \(\
eg adjacent(u,v)\to x_{u}+x_{v}\leq 1\) (Rule 4). In addition, a candidate vertex adjacent to all vertices in the current clique is forced into the clique (Rule 5) and a vertices of degree too low to contribute to the growing clique is rejected (Rule 7). The branch and bound search selects variables dynamically based on current degree in the candidate set: A _non-greedy_ selection chooses a vertex of lowest degree and _greedy_ selects highest degree. The computational results showed that greedy was good for (easy) sparse graphs and non-greedy was good for (hard) dense graphs. **1994:** In [22] [PERSON] and [PERSON] reviewed algorithms for the enumeration problem (counting maximal cliques) and exact algorithms for the maximum clique problem. Although dated, it continues to be an excellent review. **1997:** In [14] graph colouring and fractional colouring is used to bound search. Comparing again to MC (Listing 1) the candidate set is coloured greedily, and if the size of the current clique plus the number of colours used is less than or equal to the size of the largest clique found so far, that branch of search is cut off. In [14] vertices are selected in non-increasing degree order, the opposite of that proposed by [8]. We can get a similar effect to [14] in MC if we allow free selection of vertices, colour \(newP\) between lines 42 and 43 and make the recursive call to \(expand\) in line 43 conditional on the colour bound. **2002:** [PERSON] proposed an algorithm that has a dynamic programming flavour [7]. The search process starts by finding the largest clique containing vertices drawn from the set \(S_{n}=\{v_{n}\}\) and records it size in \(c[n]\). Search then proceeds to find the largest clique in the set \(S_{i}=\{v_{i},v_{i+1},...,v_{n}\}\) using the value in \(c[i+1]\) as a bound. The vertices are ordered at the top of search in colour order, _i.e._, the vertices are coloured greedily and then ordered in non-decreasing colour order, similar to that in \(numberSort\) Listing 4. [PERSON]'s algorithm is available as Cliquer [7]. In the same year, [PERSON] [4] presented a simple algorithm (Algorithm 1) that is essentially MC but with a free selection of vertices rather than the fixed iteration in line 36 of Listing 1 and dynamic maintenance of vertex degree in the candidate set. This is then enhanced (Algorithm 2) with forced accept and forced reject steps similar to Rules 4, 5 and 7 of [8] and the algorithm is named \(DF\) (\(D\)omain \(F\)ltering). DF is thenenhanced to incorporate a colouring bound, similar to that in Wood [14]. **2003:** [PERSON] proposed a constraint programming model for the maximum clique problem [9]. His model uses a matching in a duplicated graph to deliver a bound within search, a _Not Set_ as used in the Bron Kerbosch enumeration Algorithm 457 [23] and vertex selection using the pivoting strategy similar to that in [16, 23, 24, 25]. That same year [PERSON] reported MCQ [12]. **2004:** [PERSON] _et al._[26] presented a number of _kernelization_ steps to reduce a graph before and during search in the vertex cover problem, where a minimum vertex cover of the complement graph is a maximal clique in the original graph. Some of the kernelization steps are similar to the pruning rules in [4, 8] although _Crown Reduction_ appears to be novel and effective. **2007:** [PERSON] proposed MCR [15] and in the same year [PERSON] and [PERSON] proposed the _MaxCliqueDyn_ algorithm [5]. The algorithm is essentially MCQ [12] with dynamic reordering of vertices in the candidate set, using current degree, prior to colouring.