Volume 57, Number 3, May-June 2023
|Page(s)||1559 - 1578|
|Published online||26 June 2023|
A biased random-key genetic algorithm for the chordal completion problem
Universidade Federal Fluminense, Institute of Computing, Niterói, RJ 24210-240, Brazil
* Corresponding author: firstname.lastname@example.org
Accepted: 30 May 2023
A graph is chordal if all its cycles of length greater than or equal to four contain a chord, i.e., an edge connecting two nonconsecutive vertices of the cycle. Given a graph G = (V, E), the chordal completion problem consists in finding the minimum set of edges to be added to G to obtain a chordal graph. It has applications in sparse linear systems, database management and computer vision programming. In this article, we developed a biased random-key genetic algorithm (BRKGA) for solving the chordal completion problem, based on the strategy of manipulating permutations that represent perfect elimination orderings of triangulations. Computational results show that the proposed heuristic improve the results of the constructive heuristics fill-in and min-degree. We also developed a strategy for injecting externally constructed feasible solutions coded as random keys into the initial population of the BRKGA that significantly improves the solutions obtained and may benefit other implementations of biased random-key genetic algorithms.
Mathematics Subject Classification: 05C85 / 90-05
Key words: chordal completion / Chordal graphs / Biased random-key genetic algorithm / BRKGA / Metaheuristics / Fill-in / Combinatorial optimization
© The authors. Published by EDP Sciences, ROADEF, SMAI 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.