Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Este artigo descreve uma metodologia gulosa idealizada para buscar uma solução ótima para o problema da k-dispersão em grafos, bem como a implementação aplicada para este fim. A abordagem proposta consiste em aplicar uma poda inicial nas arestas de um grafo completo sem eliminar a solução ótima e realizar uma busca progressiva promovendo novas podas a cada k-clique candidata encontrada, de forma a reduzir o tamanho do problema. As sucessivas podas fazem o grafo reduzir de tamanho rapidamente, o que permite que grandes instâncias também sejam tratadas. Os tempos de execução foram comparados com os obtidos pelo algoritmo “branch-and-bound” por meio da execução do software CPLEX, que foi utilizado para confirmar a corretude dos resultados obtidos.