An Evolutionary Approach to the Maximum Edge Weight Clique Problem

Title:An Evolutionary Approach to the Maximum Edge Weight Clique Problem

Volume: 11 Issue: 3

Author(s): Dalila B.M.M. Fontes*, Jose Fernando Goncalves and Fernando A.C.C. Fontes

Affiliation:

• Faculdade de Economia and LIAAD-INESC TEC, Universidade do Porto, Porto,Portugal

Keywords: Genetic algorithms, network optimization, maximum clique, weight clique, genetic representation, genes.

Abstract: 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.

Cite this article as:

Fontes B.M.M. Dalila *, Goncalves Fernando Jose and Fontes A.C.C. Fernando , An Evolutionary Approach to the Maximum Edge Weight Clique Problem, Recent Advances in Electrical & Electronic Engineering 2018; 11 (3) . https://dx.doi.org/10.2174/2352096511666180214105643

DOI https://dx.doi.org/10.2174/2352096511666180214105643	Print ISSN 2352-0965
Publisher Name Bentham Science Publisher	Online ISSN 2352-0973