info:eu-repo/semantics/article
Neural Network Models for the Maximum Clique Problem
Registro en:
0257-4306
2224-5405
Autor
López Reyes, Nancy
Cruz Rodés, Roberto
Institución
Resumen
ABSTRACT: In this paper we describe two neural network based algorithms for the Maximum Clique Problem. The developed algorithms provide discrete and continuos descent dynamics respectively to approximate the
solution of the quadratic 0-1 formulation of the Maximum Clique Problem. The discrete approach
performed better, maintaining computational competitiveness to greedy randomized search procedures.
Experimental results on test graphs of size up to 3361 vertices and 5506380 edges are presented. RESUMEN: Se describen dos algoritmos basados en redes neuronales para el Problema del Clique Máximo de un grafo. Los algoritmos desarrollados implementan dinámicas descendentes, en un caso continua y en el
otro discreta, para aproximar la solución del problema planteado a partir de la formulación cuadrática
del mismo. El algoritmo discreto presenta un mejor desempeño, alcanzando resultados similares a los
obtenidos con otras heurísticas. Se discuten los resultados de la aplicación de los algoritmos en un
conjunto de grafos de hasta 3361 vértices y 5506380 aristas. COL0024365