An Evolutionary Approach to the Maximum Edge Weight Clique Problem

• Tipo: Artigo em Revista Científica Internacional
• Data: 2018

Autores

Dalila B. M. M. Fontes (Autor) FEP; José Fernando Gonçalves (Autor) FEP; Fernando A. C. C. Fontes (Autor) FEUP

Revista

Título: Recent Advances in Electrical and Electronic Engineering

Vol. 11 Nº 3

Páginas: 260-266

ISSN: 2352-0965

Editora: Bentham Science

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 7 Citações

Outras Informações

ID Authenticus: P-00P-GE7

DOI: 10.2174/2352096511666180214105643

Abstract (EN): Background: This work addresses the maximum edge weight clique problem (MEWC), an important generalization of the well-known maximum clique problem. Methods: The MEWC problem can be used to model applications in many fields including broadband network design, computer vision, pattern recognition, and robotics. We propose a random key genetic algorithm to find good quality solutions for this problem. Computational experiments are reported for a set of benchmark problem instances derived from the DIMACS maximum clique instances. Results: The results obtained show that our algorithm is both effective and efficient, as for most of the problem instances tested, we were able to match the best-known solutions with very small computational time requirements.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 7