http://repositorio.ufc.br/handle/riufc/24014 2026-05-15T22:53:45Z http://repositorio.ufc.br/handle/riufc/75578 Título: Heurística probabilística guiada pelos potenciais dos vértices para o problema do corte máximo Autor(es): Castro Filho, José Arimateia Fabricio de Abstract: The Max Cut Problem consists of dividing the vertices of a graph into two sets so that the sum of the edge weights between these two sets is as high as possible. The problem is NP-Hard and to the best of our knowledge there is still no method or work in the literature that has managed to obtain the optimal value of instances with large sizes. In this work we propose a new heuristic that is given by combining a local search, guided by the internal and external potentials of the vertices, with the use of probability to create an initial solution. We present computational experiments on 54 instances known from the literature and other created instances. The results obtained are compared with a work in the literature that is considered the best among those that also use probability to compose a resolution method for the max cut Tipo: TCC 2021-01-01T00:00:00Z