Neural Network Models for the Maximum Clique Problem

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.

• Autores: López Reyes, Nancy; Cruz Rodés, Roberto
• Tipo de recurso: Article of investigation
• Fecha de publicación: 2000
• Institución: Universidad de Antioquia
• Repositorio: Repositorio UdeA
• Idioma: eng
• OAI Identifier: oai:bibliotecadigital.udea.edu.co:10495/34430
• Acceso en línea: https://hdl.handle.net/10495/34430
• Palabra clave: Heurística; Heuristics; Redes Neurales de la Computación; Neural Networks, Computer; Optimización combinatoria; Combinatorial optimization; Teoría de función geométrica; Geometric function theory; Problema del clique máximo; Problema cuadrático 0-1; https://id.nlm.nih.gov/mesh/D000066506; https://id.nlm.nih.gov/mesh/D016571
• Rights: openAccess
• License: https://creativecommons.org/licenses/by-nc-nd/4.0/