<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Given an undirected connected graph <italic>G</italic> = (<italic>V, E</italic>), a subset of vertices <italic>S</italic> is a maximum 2-packing set if the number of edges in the shortest path between any pair of vertices in <italic>S</italic> is at least 3 and <italic>S</italic> has the maximum cardinality. In this paper, we present a genetic algorithm for the maximum 2-packing set problem on arbitrary graphs, which is an NP-hard problem. To the best of our knowledge, this work is a pioneering effort to tackle this problem for arbitrary graphs. For comparison, we extended and outperformed a well-known genetic algorithm originally designed for the maximum independent set problem. We also compared our genetic algorithm with a polynomial-time one for the maximum 2-packing set problem on cactus graphs. Empirical results show that our genetic algorithm is capable of finding 2-packing sets with a cardinality relatively close (or equal) to that of the maximum 2-packing sets. Moreover, the cardinality of the 2-packing sets found by our genetic algorithm increases linearly with the number of vertices and with a larger population and a larger number of generations. Furthermore, we provide a theoretical proof demonstrating that our genetic algorithm increases the fitness for each candidate solution when certain conditions are met.</p></abstract>

Given an undirected connected graph G = (V, E), a subset of vertices S is a maximum 2-packing set if the number of edges in the shortest path between any pair of vertices in S is at least 3 and S has the maximum cardinality. In this paper, we present a genetic algorithm for the maximum 2-packing set problem on arbitrary graphs, which is an NP-hard problem. To the best of our knowledge, this work is a pioneering effort to tackle this problem for arbitrary graphs. For comparison, we extended and outperformed a well-known genetic algorithm originally designed for the maximum independent set problem. We also compared our genetic algorithm with a polynomial-time one for the maximum 2-packing set problem on cactus graphs. Empirical results show that our genetic algorithm is capable of finding 2-packing sets with a cardinality relatively close (or equal) to that of the maximum 2-packing sets. Moreover, the cardinality of the 2-packing sets found by our genetic algorithm increases linearly with the number of vertices and with a larger population and a larger number of generations. Furthermore, we provide a theoretical proof demonstrating that our genetic algorithm increases the fitness for each candidate solution when certain conditions are met.

A Genetic Algorithm for the Maximum 2–Packing Set Problem

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"A Genetic Algorithm for the Maximum 2\u2013Packing Set Problem"}

Given an undirected connected graph G = (V, E), a subset of vertices S is a maximum 2-packing set if the number of edges in the shortest path between any pair...

A Genetic Algorithm for the Maximum 2–Packing Set Problem

Publié en ligne: 03 avr. 2020

Pages: 173 - 184

Reçu: 01 févr. 2019

Accepté: 07 sept. 2019

DOI: https://doi.org/10.34768/amcs-2020-0014

Mots clés
maximum 2-packing set, genetic algorithms, graph algorithms

© 2020 Joel Antonio Trejo-Sánchez et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

A Genetic Algorithm for the Maximum 2–Packing Set Problem

Publié en ligne: 03 avr. 2020

Pages: 173 - 184

Reçu: 01 févr. 2019

Accepté: 07 sept. 2019

DOI: https://doi.org/10.34768/amcs-2020-0014

Mots clésmaximum 2-packing set, genetic algorithms, graph algorithms

© 2020 Joel Antonio Trejo-Sánchez et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
maximum 2-packing set, genetic algorithms, graph algorithms