Autor:

Trejo-Sánchez, Joel Antonio ; Fajardo-Delgado, Daniel ; Gutierrez-Garcia, J. Octavio

Współtwórca:

Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.

Tytuł:

A genetic algorithm for the maximum 2-packing set problem

Tytuł publikacji grupowej:

AMCS, volume 30 (2020)

Temat i słowa kluczowe:

maximum 2-packing set ; genetic algorithms ; graph algorithms

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.

Wydawca:

Zielona Góra: Uniwersytet Zielonogórski

Data wydania:

2020

Typ zasobu:

artykuł

DOI:

10.34768/amcs-2020-0014

Strony:

173-184

Źródło:

AMCS, volume 30, number 1 (2020) ; kliknij tutaj, żeby przejść

Jezyk:

eng

Licencja CC BY 4.0:

kliknij tutaj, żeby przejść

Prawa do dysponowania publikacją:

Biblioteka Uniwersytetu Zielonogórskiego