Skip to content

README.md

Latest commit

 

History

History
28 lines (16 loc) · 1.16 KB

README.md

File metadata and controls

28 lines (16 loc) · 1.16 KB
Raw

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.