Genetic Algorithm for Finding the Global Forcing Number of Bipartite Graphs
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 forc...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Kashan
2024-12-01
|
| Series: | Mathematics Interdisciplinary Research |
| Subjects: | |
| Online Access: | https://mir.kashanu.ac.ir/article_114587_4bbc4481b71a33e5339aa3d938a8b404.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850111228693708800 |
|---|---|
| author | Sara Oskoueian Mostafa Tavakoli Narjes Sabeghi |
| author_facet | Sara Oskoueian Mostafa Tavakoli Narjes Sabeghi |
| author_sort | Sara Oskoueian |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-082a7185d79149c98ba776675c98da3e |
| institution | OA Journals |
| issn | 2476-4965 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | University of Kashan |
| record_format | Article |
| series | Mathematics Interdisciplinary Research |
| spelling | doaj-art-082a7185d79149c98ba776675c98da3e2025-08-20T02:37:39ZengUniversity of KashanMathematics Interdisciplinary Research2476-49652024-12-019441342410.22052/mir.2024.255203.1472114587Genetic Algorithm for Finding the Global Forcing Number of Bipartite GraphsSara Oskoueian0Mostafa Tavakoli1Narjes Sabeghi2Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, I. R. IranDepartment of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, I. R. IranDepartment of Mathematics, Faculty of Basic Sciences, Velayat UniversityConsider 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.https://mir.kashanu.ac.ir/article_114587_4bbc4481b71a33e5339aa3d938a8b404.pdfperfect matchingglobal forcing setgenetic algorithmhexagonal system |
| spellingShingle | Sara Oskoueian Mostafa Tavakoli Narjes Sabeghi Genetic Algorithm for Finding the Global Forcing Number of Bipartite Graphs Mathematics Interdisciplinary Research perfect matching global forcing set genetic algorithm hexagonal system |
| title | Genetic Algorithm for Finding the Global Forcing Number of Bipartite Graphs |
| title_full | Genetic Algorithm for Finding the Global Forcing Number of Bipartite Graphs |
| title_fullStr | Genetic Algorithm for Finding the Global Forcing Number of Bipartite Graphs |
| title_full_unstemmed | Genetic Algorithm for Finding the Global Forcing Number of Bipartite Graphs |
| title_short | Genetic Algorithm for Finding the Global Forcing Number of Bipartite Graphs |
| title_sort | genetic algorithm for finding the global forcing number of bipartite graphs |
| topic | perfect matching global forcing set genetic algorithm hexagonal system |
| url | https://mir.kashanu.ac.ir/article_114587_4bbc4481b71a33e5339aa3d938a8b404.pdf |
| work_keys_str_mv | AT saraoskoueian geneticalgorithmforfindingtheglobalforcingnumberofbipartitegraphs AT mostafatavakoli geneticalgorithmforfindingtheglobalforcingnumberofbipartitegraphs AT narjessabeghi geneticalgorithmforfindingtheglobalforcingnumberofbipartitegraphs |