Clique Máxima

Implementação de algoritmo de encontrar a clique máxima de um grafo para a disciplina de Algoritmos Avançados do curso de Ciência da Computação da UFRN em 2013.

Implementação

Foram implementados dois algoritmos para o problema:

1. Algoritmo exato - lento mas garante a resposta correta.
2. Algoritmo probabilístico - rápido mas não garante a resposta correta.

Solução inicial

Ambas as implementações são iniciadas gerando uma clique inicial através da implementação do algoritmo DSatur [1].

Algoritmo exato

O algoritmo exato foi implementado usando as técnicas de Backtracking e de Branch-And-Bound, tendo como base o algoritmo de Bron e Kerbosch [2].

Algoritmo probabilístico

O algoritmo probabilístico foi implementado usando a técnica meta-heurística de Busca Tabu, tendo como base o algoritmo de Gendreau [3].

Referências

• [1] BRELAZ, 1979. New methods to color the vertices of a graph.
• [2] BRON & KERBOSCH, 1973. Finding all cliques of an undirected graph.
• [3] GENDREAU, 1993. Solving the maximum clique problem using a tabu search approach.