HEURÍSTICA PROBABILÍSTICA GUIADA PELOS POTENCIAIS DO VÉRTICES PARA O PROBLEMA DO CORTE MÁXIMO

O Problema do Corte Máximo (\textit{Max-Cut}) consiste em dividir os vértices de um grafo em dois conjuntos de forma que o somatório dos pesos das arestas entre esses dois conjuntos seja o maior possível. O problema é NP-Difícil e no melhor do nosso conhecimento ainda não existe um método ou trabalho na literatura que tenha conseguido obter o valor ótimo de instâncias com tamanhos grandes. Neste trabalho, propomos uma nova heurística que é dada pela combinação de uma busca local, guiada pelos potenciais internos e externos dos vértices, com o uso de probabilidade para criar uma solução inicial. Apresentamos experimentos computacionais em $54$ instâncias conhecidas da literatura e outras instâncias criadas. Os resultados obtidos são comparados com um trabalho da literatura que é considerado o melhor dentre aqueles que também usam probabilidade para compor um método de resolução para o \textit{max-cut}.