Algoritmo GRASP-VND para o problema da máxima biclique balanceada com peso no vértice

Vol 52, 2020 - 127110
Prêmio de IC
Favorite this paper
How to cite this paper?
Abstract

Este trabalho trata do problema da máxima biclique balanceada com peso no vértice. Dado um grafo não direcionado com peso nos vértices, o objetivo do problema é encontrar uma biclique (subgrafo bipartite completo) balanceada que possua o máximo somatório dos pesos. Além de ser um problema NP-difícil, possui diversas aplicações preeminentes. Este artigo propõe uma meta-heurística GRASP com uso de uma busca local VND com três estruturas de vizinhança. A heurística proposta foi avaliada nas instâncias da literatura (DIMACS e BHOSLIB) e os resultados indicam que o algoritmo proposto, em comparação com o algoritmo exato CPLEX, foi capaz de encontrar todas as soluções ótimas conhecidas em um baixo tempo computacional.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Federal de Alagoas
Track
  • 13. MH – Metaheurísticas
Keywords
Biclique
meta-heurística
Otimização Combinatória