# The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
## 3 Minor Improvements in HTS2
Results for BHOSLIB instances are given in Table 5, and results for all other instances are given in Table 6. In these two tables, the first column gives the instance, and the second column gives the number of vertices in the largest known clique (marked with an asterisk if the clique is known to be optimal). The third, fourth, and fifth columns give the time in seconds to find the solution in column 2, with a note of the number of vertices found if the result in column 2 is not achieved. \begin{table}
\begin{tabular}{l c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multicolumn{2}{c}{**Optimal or Best Known**} & \multirow{2}{*}{**HTS (s)**} & \multirow{2}{*}{**HTS2 (s)**} & \multirow{2}{*}{**SBTS (s)**} \\  & \multicolumn{2}{c}{**Number of Vertices**} & & \\ \hline
1 dc.1024 & 94 * & 11,899 & 8 & \textless{}1 \\
1 dc.2048 & 172 & 20,561 & 324 & \textless{}1 \\
1 et.1024 & 171 * & 25,988 & 1485 & \textless{}1 \\
1 et.2048 & 316 * & 1366 & 5219 & 119.5 \\
1 tc.1024 & 196 * & 1309 & 69 & \textless{}1 \\
1 tc.2048 & 352 * & 797 & 19,786 & 773.5 \\
1 zc.1024 & 112 & 8880 & 445 & 2.7 \\
1 zc.2048 & 198 & 15,477 & 2366 & 23.6 \\
2 dc.1024 & 16 * & 51 & \textless{}1 & \textless{}1 \\
2 dc.2048 & 24 * & 131 & 34 & \textless{}1 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Comparison of run times to find optimal or best known solution of Sloane, DIMACS, and permutation code instances for HTS, HTS2, and SBTS. If the solution in the second column is not achieved, the best solution found is indicated in brackets. * denotes that the best known result is optimal. \begin{table}
\begin{tabular}{l c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multicolumn{2}{c}{**Optimal or Best Known**} & \multirow{2}{*}{**HTS (s)**} & \multirow{2}{*}{**HTS2 (s)**} & \multirow{2}{*}{**SBTS (s)**} \\  & **Number of Vertices** & & & \\ \hline frb30-15-1 & 30 * & 20 & 13 & \textless{}1 \\ frb30-15-2 & 30 * & 3 & \textless{}1 & \textless{}1 \\ frb30-15-3 & 30 * & 16 & 38 & \textless{}1 \\ frb30-15-4 & 30 * & 14 & 1 & \textless{}1 \\ frb30-15-5 & 30 * & 38 & 24 & \textless{}1 \\ frb35-17-1 & 35 * & 175 & 53 & \textless{}1 \\ frb35-17-2 & 35 * & 7 & 11 & \textless{}1 \\ frb35-17-3 & 35 * & 29 & 2 & \textless{}1 \\ frb35-17-4 & 35 * & 807 & 129 & 2.7 \\ frb35-17-5 & 35 * & 138 & 9 & 1.2 \\ frb40-19-1 & 40 * & 20 & 1 & \textless{}1 \\ frb40-19-2 & 40 * & 555 & 123 & 25.7 \\ frb40-19-3 & 40 * & 77 & 1 & 7.2 \\ frb40-19-4 & 40 * & 1394 & 32 & 1.1 \\ frb40-19-5 & 40 * & 6804 & 2000 & 28.1 \\ frb45-21-1 & 45 * & 9692 & 5778 & 16.0 \\ frb45-21-2 & 45 * & 57,227 & 379 & 5.5 \\ frb45-21-3 & 45 * & 93,925 & 2568 & 16.7 \\ frb45-21-4 & 45 * & 12,123 & 1690 & 31.6 \\ frb45-21-5 & 45 * & 111,435 & 2173 & 18.0 \\ frb50-23-1 & 50 * & 22,883 & 10,649 & 67.0 \\ frb50-23-2 & 50 * & 90,753 & 1219 & 571.4 \\ frb50-23-3 & 50 * & 196,389 & 17,472 & 2098.4 \\ frb50-23-4 & 50 * & 119 & 295 & 54.4 \\ frb50-23-5 & 50 * & 563 & 350 & 80.8 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comparison of run times to find optimal solution of BHOSLIB instances for HTS, HTS2, and SBTS (Swap-Based Tabu Search). * denotes that the best known result is optimal. For most instances, HTS2 is faster than HTS and finds a larger clique for C2000_9 than HTS without pre-processing, and also a larger clique for 7_5 than HTS with or without pre-processing. For BHOSLIB, most DIMACS and Sloane code construction instances, SBTS is much faster than HTS2, as might be expected. However, HTS2 is more competitive on harder DIMACS instances, such as C2000_9, and performs much better than SBTS on 7_5 and 8_5 cyclic.