Sea un grafo no dirigido con un conjunto de vértices y un conjunto de aristas . Una clique de es un subconjunto de los vértices de con cada par de vértices adyacentes. Una clique máxima es una clique con el número máximo de vértices. Se presenta un algoritmo de búsqueda tabú para el problema de la clique máxima que utiliza un algoritmo exacto en subproblemas. El algoritmo exacto utiliza un límite superior de coloración de grafos para la poda, y se considera el mejor algoritmo para usar en este contexto. El algoritmo de búsqueda tabú final encuentra con éxito la solución óptima o mejor conocida para todos los benchmarks estándar considerados. Se compara con un algoritmo de vanguardia que no utiliza búsqueda exacta. Es más lento para encontrar la solución óptima conocida en la mayoría de los casos, pero es más rápido para cinco casos y encuentra una clique más grande para dos casos.