Volume: 5 Issue 12 [December 2022]

Article:An efficient method to solve minimum spanning tree problem using graph theory and improved ant colony optimization algorithm

Author: K.P.O.Niluminda, E.M.U.S.B.Ekanayake

Volume: Vol 5, Issue 12; December 2022

DOI: North American Academic Research, 5(12) 34-43 December 2022, https://doi.org/10.5281/zenodo.7459058

Abstract: A specific type of graph G is a spanning tree. A spanning tree is produced when all of the vertices of a connected undirected graph G are connected by the fewest number of edges possible. For a graph, there may be several such spanning trees. However, the term "Minimum Spanning Tree" (MST) refers to a connected, edge-weighted, undirected network that has all of its vertices connected, is cycle-free, and has the least amount of total edge weight. Several algorithms have been developed by researchers to find MST. Prim’s and Kruskal's algorithms are famous algorithms developed to find the MST of an undirected connected graph. In 1990, the Ant Colony Opti-mization (ACO) approach developed and it has been solely motivated by the foraging behavior of ant colonies. Ants are eusocial insects that want to thrive and survive as a group rather than as a single species. Pheromones, touch, and sound are the main means of communication between them. The ants release pheromones, which are organic chem-ical substances that cause other members of their species to act socially. In this study, we proposed a new probability-based algorithm to find the MST of undirected connected graphs using an improved ACO algorithm. The proposed method is then shown using numerical examples and compared with existing MST algorithms. We get outcomes that are on par with those of the algorithms developed by Prim and Kruskal.

Comments