An Evolutionary Approach to the Maximum Edge Weight Clique Problem

• Type: Article in International Scientific Journal
• Date: 2018

Authors

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

Journal

Title: Recent Advances in Electrical and Electronic Engineering

Vol. 11 No. 3

Pages: 260-266

ISSN: 2352-0965

Publisher: Bentham Science

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 7 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 7