Object
Title: A genetic algorithm for the maximum 2-packing set problem
Creator:
Trejo-Sánchez, Joel Antonio ; Fajardo-Delgado, Daniel ; Gutierrez-Garcia, J. Octavio
Date:
Resource Type:
Contributor:
Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.
Group publication title:
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.
Publisher:
Zielona Góra: Uniwersytet Zielonogórski
Resource Identifier:
DOI:
Pages:
Source:
AMCS, volume 30, number 1 (2020) ; click here to follow the link
Language:
License CC BY 4.0:
Rights:
Biblioteka Uniwersytetu Zielonogórskiego
Object collections:
- Digital Library of Zielona Góra > Repository > Faculties > Faculty of Computer, Electrical and Control Engineering
- Digital Library of Zielona Góra > Repository > Types of work > Articles
- Digital Library of Zielona Góra > Repository > Scientific journals and UZ publishing series > International Journal of Applied Mathematics and Computer Science (AMCS) > International Journal of Applied Mathematics and Computer Science (AMCS) (2020)
Last modified:
Jul 15, 2025
In our library since:
Jul 15, 2025
Number of object content hits:
6
All available object's versions:
https://zbc.uz.zgora.pl/publication/101094
Show description in RDF format:
Show description in OAI-PMH format:
-
International Journal of Applied Mathematics and Computer Science (AMCS)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 35 (2025)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 34 (2024)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 33 (2023)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 32 (2022)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 31 (2021)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 30 (2020)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 30, number 1 (2020)
- International Journal of Applied Mathematics and Computer Science (AMCS), volume 30, number 1 (2020) - Contents
- Input reconstruction by feedback control for the Schlögl and FitzHugh-Nagumo equations
- An information based approach to stochastic control problems
- Nonlinear model predictive control for processes with complex dynamics: A parameterisation approach using Laguerre functions
- Health-aware and fault-tolerant control of an octorotor UAV system based on actuator reliability
- Fault tolerant multicontrollers for nonlinear systems: A real validation on a chemical process
- Extremal properties of linear dynamic systems controlled by Dirac`s impulse
- Anti-periodic solutions for Clifford-valued high-order Hopfield neural networks with state-dependent and leakage delays
- Finding robust transfer features for unsupervised domain adaptation
- A second-order TV-based coupling model and an ADMM algorithm for MR image reconstruction
- Curve skeleton extraction via k-nearest-neighbors based contraction
- A quaternion clustering framework
- An algorithm for quaternion-based 3D rotation
- Heuristic search of exact biclusters in binary data
- A genetic algorithm for the maximum 2-packing set problem
- A decomposition approach to type 2 interval arithmetic
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 30, number 2 (2020)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 30, number 3 (2020)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 30, number 4 (2020)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 30, number 1 (2020)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 29 (2019)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 28 (2018)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 27 (2017)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 26 (2016)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 25 (2015)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 24 (2014)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 23 (2013)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 22 (2012)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 21 (2011)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 20 (2010)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 19 (2009)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 18 (2008)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 17 (2007)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 16 (2006)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 15 (2005)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 13 (2003)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 12 (2002)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 11 (2001)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 10 (2000)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 9 (1999)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 8 (1998)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 7 (1997)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 6 (1996)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 5 (1995)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 4 (1994)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 3 (1993)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 2 (1992)
-
International Journal of Applied Mathematics and Computer Science (AMCS),volume 1 (1991)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 35 (2025)
| Edition name | Date |
|---|---|
| A genetic algorithm for the maximum 2-packing set problem | Jul 15, 2025 |
