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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2476-4965 |