Genetic Algorithm for Finding the Global Forcing Number of Bipartite Graphs
نویسندگان
1 Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, I. R. Iran
2 Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, I. R. Iran
3 Department of Mathematics, Faculty of Basic Sciences, Velayat University
doi
10.22052/mir.2024.255203.1472چکیده
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.
