UN ALGORITMO DEL MÉTODO DE INTEGRACIÓN DE VARIABLES PARA LA SOLUCIÓN DEL PROBLEMA MÁXIMO CLIQUE PONDERADO

Abstract

In an undirected graph with positive weights on the vertices, the maximum weight clique problem is to find a complete subgraph with maximum sum of vertices weights. This problem is NP-complete. In the present work is proposed a heuristic algorithm based in the Integration of Variables Method for the maximum weight clique problem. A new coding system to the representation of the problem by the Integration of Variables Method is showed. The operators to evolve the population’s code are defined. The algorithm is tested with DIMACS graphs and for generated random graphs. The results are compared with results of Lemke’s method. Tests have shown that different stop criteria can be used to apply the algorithm to the needs of a particular