| Autor: |
Sara Oskoueian, Mostafa Tavakoli, Narjes Sabeghi |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Mathematics Interdisciplinary Research, Vol 9, Iss 4, Pp 413-424 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2476-4965 |
| DOI: |
10.22052/mir.2024.255203.1472 |
| Popis: |
Consider a graph $G=(V(G),E(G))$, where a perfect matching in $G$ is defined as a subset of independent edges with $\frac{|V(G)|}{2}$ elements. A global forcing set is a subset $S$ of $E$ such that no two disjoint perfect matchings of $G$ coincide on it. The minimum cardinality of global forcing sets of $G$ is called the global forcing number (GFN for short). This paper addresses the NP-hard problem of determining the global forcing number for perfect matchings. The focus is on a Genetic Algorithm (GA) that utilizes binary encoding and standard genetic operators to solve this problem. The proposed algorithm is implemented on some chemical graphs to illustrate the validity of the algorithm. The solutions obtained by the GA are compared with the results from other methods that have been presented in the literature. The presented algorithm can be applied to various bipartite graphs, particularly hexagonal systems. Additionally, the results of the GA improve some results that have already been presented for finding GFN. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
