An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm

Kankanam Pathiranage Oshan Niluminda; Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake

doi:doi:10.11648/j.ajam.20221006.11

| Peer-Reviewed

An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm

Kankanam Pathiranage Oshan Niluminda, Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake

Published in American Journal of Applied Mathematics (Volume 10, Issue 6)

Received: 22 October 2022 Accepted: 4 November 2022 Published: 8 December 2022

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

In real life, people often want to do tasks at the lowest possible cost while also taking into consideration travel time and distance. The term "minimum spanning tree" refers to the spanning tree that has a weight that is less than or equal to the weight of all other feasible spanning trees. A spanning tree is created when every vertex in a network is linked and has no cycles in it; there must be no other spanning tree with a lesser weight. The minimum spanning tree problem has been solved using a variety of methods that have been published in the literature. They provide the best answer to the minimum spanning tree problems given an undirected graph using Prim's and Kruskal's algorithms. A probabilistic method for resolving computational issues that may be simplified to finding the best route via graphs is the Ant Colony Optimization Algorithm (ACOA). This algorithm has been developed based on how ants search for a route between their nest and a food source while foraging. This paper proposes a novel technique and effective method for studying the large scale of the problem and determining the minimum cost-spanning tree of a connected weight undirected graph with fewer iterations using the Modified Ant Colony Optimization Algorithm (ACOA). When the graph has a large number of nodes, this novel approach is simpler and easier to implement than other existing algorithms, and by comparing our methods to Prim's and Kruskal's, we can get the same results.

Published in	American Journal of Applied Mathematics (Volume 10, Issue 6)
DOI	10.11648/j.ajam.20221006.11
Page(s)	223-235
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Ant Colony Algorithm, A Minimum Weight Spanning Tree, Prim’s Algorithm, Kruskal’s Algorithm, Undirected Graph

References

[1]	J. Nešetřil, E. Milková, and H. Nešetřilová, “Otakar Borůvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history,” Discrete Math., vol. 233, no. 1–3, pp. 3–36, Apr. 2001, doi: 10.1016/S0012-365X(00)00224-7.
[2]	Dey, S. Broumi, L. H. Son, A. Bakali, M. Talea, and F. Smarandache, “A new algorithm for finding minimum spanning trees with undirected neutrosophic graphs,” Granul. Comput., vol. 4, no. 1, pp. 63–69, 2019, doi: 10.1007/s41066-018-0084-7.
[3]	Khan, A. A. Aesha, and J. Sarker, “A new algorithmic approach to finding minimum spanning tree,” 4th Int. Conf. Electr. Eng. Inf. Commun. Technol. iCEEiCT 2018, pp. 590–594, Jan. 2019, doi: 10.1109/CEEICT.2018.8628095.
[4]	P. Biswas, M. Goel, H. Negi, and M. Datta, “An Efficient Greedy Minimum Spanning Tree Algorithm Based on Vertex Associative Cycle Detection Method,” Procedia Comput. Sci., vol. 92, pp. 513–519, Jan. 2016, doi: 10.1016/J.PROCS.2016.07.376.
[5]	U. Ekanayake, W. Daundasekara, and P. Perera, “Research An Approach for Solving Minimum Spanning Tree Problem and Transportation Problem Using Modified Ant Colony Algorithm,” North Am. Acad. Res., vol. 3, no. 9, pp. 28–45, 2020, doi: 10.5281/zenodo.4072472.
[6]	P. Ayegba, J. Ayoola, E. Asani, and A. Okeyinka, “A Comparative Study of Minimal Spanning Tree Algorithms,” 2020 Int. Conf. Math. Comput. Eng. Comput. Sci. ICMCECS 2020, no. May 2020, doi: 10.1109/ICMCECS47690.2020.240900.
[7]	H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica, vol. 6, no. 2, pp. 109–122, Jun. 1986, doi: 10.1007/BF02579168.
[8]	M.-B. Choi and S.-U. Lee, “An Efficient Implementation of Kruskal’s and Reverse-Delete Minimum Spanning Tree Algorithm,” J. Inst. Webcasting, Internet Telecommun., vol. 13, no. 2, pp. 103–114, Apr. 2013, doi: 10.7236/JIIBC.2013.13.2.103.
[9]	Colorni, A., Dorigo, M. and Maniezzo, V. (1991) Distributed Optimization by Ant Colonies. In Varela, F. and Bourgine, P., Eds., Proceedings of the European Conference on Artificial Life, ECAL’91, Paris, Elsevier Publishing, Amsterdam, 134-142. - Reference.
[10]	A. Alsawy and H. A. Hefny, “Fuzzy-based ant colony optimization algorithm,” ICCTD 2010 - 2010 2nd Int. Conf. Comput. Technol. Dev. Proc., pp. 530–534, 2010, doi: 10.1109/ICCTD.2010.5645952.
[11]	U. Jaiswal and S. Aggarwal, “Ant Colony Optimization,” Int. J. Sci. Eng. Res., vol. 2, no. 7, 2011.
[12]	John Clark and Derek Allan Holton (1995)‘A First Look At Graph Theory’, published by Allied Publishers Limited, 1995 - Google Search.
[13]	SAYLI and J. H. S. Alkhalissi, “Negligence Minimum Spanning Tree Algorithm,” Eur. J. Sci. Technol., no. November, pp. 70–76, 2018, doi: 10.31590/ejosat.386716.
[14]	Paryati and K. Salahddine, “The Implementation of Kruskal’s Algorithm for Minimum Spanning Tree in a Graph,” MATEC Web Conf., vol. 348, p. 01001, 2021, doi: 10.1051/matecconf/202134801001.
[15]	E. M. U. S. B. Ekanayake, S. P. C. Perera, W. B. Daundasekara, and Z. A. M. S. Juman, “A Modified Ant Colony Optimization Algorithm for Solving a Transportation Problem,” J. Adv. Math. Comput. Sci., no. August, pp. 83–101, 2020, doi: 10.9734/jamcs/2020/v35i530284.
[16]	S. Li, Y. Wei, X. Liu, H. Zhu, and Z. Yu, “A New Fast Ant Colony Optimization Algorithm: The Saltatory Evolution Ant Colony Optimization Algorithm,” Mathematics, vol. 10, no. 6, p. 925, 2022, doi: 10.3390/math10060925.
[17]	R. Likaj, A. Shala, M. Mehmetaj, P. Hyseni, and X. Bajrami, “Application of graph theory to find optimal paths for the transportation problem,” IFAC Proc. Vol., vol. 15, no. PART 1, pp. 235–240, 2013, doi: 10.3182/20130606-3-XK-4037.00031.
[18]	P. S and M. K. M, “Application Of Graph Theory To Find Optimal Path And Minimized Time For The Transportation Problem,” Int. J. Sci. Res. Publ., vol. 11, no. 1, pp. 278–285, 2020, doi: 10.29322/ijsrp.11.01.2021.p10929.

Cite This Article

Plain Text BibTeX RIS

APA Style

Kankanam Pathiranage Oshan Niluminda, Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake. (2022). An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm. American Journal of Applied Mathematics, 10(6), 223-235. https://doi.org/10.11648/j.ajam.20221006.11

Copy | Download

ACS Style

Kankanam Pathiranage Oshan Niluminda; Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake. An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm. Am. J. Appl. Math. 2022, 10(6), 223-235. doi: 10.11648/j.ajam.20221006.11

Copy | Download

AMA Style

Kankanam Pathiranage Oshan Niluminda, Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake. An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm. Am J Appl Math. 2022;10(6):223-235. doi: 10.11648/j.ajam.20221006.11

Copy | Download

@article{10.11648/j.ajam.20221006.11,
  author = {Kankanam Pathiranage Oshan Niluminda and Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake},
  title = {An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm},
  journal = {American Journal of Applied Mathematics},
  volume = {10},
  number = {6},
  pages = {223-235},
  doi = {10.11648/j.ajam.20221006.11},
  url = {https://doi.org/10.11648/j.ajam.20221006.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20221006.11},
  abstract = {In real life, people often want to do tasks at the lowest possible cost while also taking into consideration travel time and distance. The term "minimum spanning tree" refers to the spanning tree that has a weight that is less than or equal to the weight of all other feasible spanning trees. A spanning tree is created when every vertex in a network is linked and has no cycles in it; there must be no other spanning tree with a lesser weight. The minimum spanning tree problem has been solved using a variety of methods that have been published in the literature. They provide the best answer to the minimum spanning tree problems given an undirected graph using Prim's and Kruskal's algorithms. A probabilistic method for resolving computational issues that may be simplified to finding the best route via graphs is the Ant Colony Optimization Algorithm (ACOA). This algorithm has been developed based on how ants search for a route between their nest and a food source while foraging. This paper proposes a novel technique and effective method for studying the large scale of the problem and determining the minimum cost-spanning tree of a connected weight undirected graph with fewer iterations using the Modified Ant Colony Optimization Algorithm (ACOA). When the graph has a large number of nodes, this novel approach is simpler and easier to implement than other existing algorithms, and by comparing our methods to Prim's and Kruskal's, we can get the same results.},
 year = {2022}
}

Copy | Download

TY  - JOUR
T1  - An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm
AU  - Kankanam Pathiranage Oshan Niluminda
AU  - Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake
Y1  - 2022/12/08
PY  - 2022
N1  - https://doi.org/10.11648/j.ajam.20221006.11
DO  - 10.11648/j.ajam.20221006.11
T2  - American Journal of Applied Mathematics
JF  - American Journal of Applied Mathematics
JO  - American Journal of Applied Mathematics
SP  - 223
EP  - 235
PB  - Science Publishing Group
SN  - 2330-006X
UR  - https://doi.org/10.11648/j.ajam.20221006.11
AB  - In real life, people often want to do tasks at the lowest possible cost while also taking into consideration travel time and distance. The term "minimum spanning tree" refers to the spanning tree that has a weight that is less than or equal to the weight of all other feasible spanning trees. A spanning tree is created when every vertex in a network is linked and has no cycles in it; there must be no other spanning tree with a lesser weight. The minimum spanning tree problem has been solved using a variety of methods that have been published in the literature. They provide the best answer to the minimum spanning tree problems given an undirected graph using Prim's and Kruskal's algorithms. A probabilistic method for resolving computational issues that may be simplified to finding the best route via graphs is the Ant Colony Optimization Algorithm (ACOA). This algorithm has been developed based on how ants search for a route between their nest and a food source while foraging. This paper proposes a novel technique and effective method for studying the large scale of the problem and determining the minimum cost-spanning tree of a connected weight undirected graph with fewer iterations using the Modified Ant Colony Optimization Algorithm (ACOA). When the graph has a large number of nodes, this novel approach is simpler and easier to implement than other existing algorithms, and by comparing our methods to Prim's and Kruskal's, we can get the same results.
VL  - 10
IS  - 6
ER  -

Copy | Download

Author Information

Kankanam Pathiranage Oshan Niluminda

Department of Physical Sciences, Faculty of Applied Sciences, Rajarata University of Sri Lanka, Mihinthale, Sri Lanka
Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake

Department of Physical Sciences, Faculty of Applied Sciences, Rajarata University of Sri Lanka, Mihinthale, Sri Lanka

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Kankanam Pathiranage Oshan Niluminda, Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake. (2022). An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm. American Journal of Applied Mathematics, 10(6), 223-235. https://doi.org/10.11648/j.ajam.20221006.11

Copy | Download

ACS Style

Kankanam Pathiranage Oshan Niluminda; Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake. An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm. Am. J. Appl. Math. 2022, 10(6), 223-235. doi: 10.11648/j.ajam.20221006.11

Copy | Download

AMA Style

Kankanam Pathiranage Oshan Niluminda, Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake. An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm. Am J Appl Math. 2022;10(6):223-235. doi: 10.11648/j.ajam.20221006.11

Copy | Download

@article{10.11648/j.ajam.20221006.11,
  author = {Kankanam Pathiranage Oshan Niluminda and Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake},
  title = {An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm},
  journal = {American Journal of Applied Mathematics},
  volume = {10},
  number = {6},
  pages = {223-235},
  doi = {10.11648/j.ajam.20221006.11},
  url = {https://doi.org/10.11648/j.ajam.20221006.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20221006.11},
  abstract = {In real life, people often want to do tasks at the lowest possible cost while also taking into consideration travel time and distance. The term "minimum spanning tree" refers to the spanning tree that has a weight that is less than or equal to the weight of all other feasible spanning trees. A spanning tree is created when every vertex in a network is linked and has no cycles in it; there must be no other spanning tree with a lesser weight. The minimum spanning tree problem has been solved using a variety of methods that have been published in the literature. They provide the best answer to the minimum spanning tree problems given an undirected graph using Prim's and Kruskal's algorithms. A probabilistic method for resolving computational issues that may be simplified to finding the best route via graphs is the Ant Colony Optimization Algorithm (ACOA). This algorithm has been developed based on how ants search for a route between their nest and a food source while foraging. This paper proposes a novel technique and effective method for studying the large scale of the problem and determining the minimum cost-spanning tree of a connected weight undirected graph with fewer iterations using the Modified Ant Colony Optimization Algorithm (ACOA). When the graph has a large number of nodes, this novel approach is simpler and easier to implement than other existing algorithms, and by comparing our methods to Prim's and Kruskal's, we can get the same results.},
 year = {2022}
}

Copy | Download

TY  - JOUR
T1  - An Approach for Solving Minimum Spanning Tree Problem Using a Modified Ant Colony Optimization Algorithm
AU  - Kankanam Pathiranage Oshan Niluminda
AU  - Ekanayake Mudiyanselage Uthpala Senarath Bandara Ekanayake
Y1  - 2022/12/08
PY  - 2022
N1  - https://doi.org/10.11648/j.ajam.20221006.11
DO  - 10.11648/j.ajam.20221006.11
T2  - American Journal of Applied Mathematics
JF  - American Journal of Applied Mathematics
JO  - American Journal of Applied Mathematics
SP  - 223
EP  - 235
PB  - Science Publishing Group
SN  - 2330-006X
UR  - https://doi.org/10.11648/j.ajam.20221006.11
AB  - In real life, people often want to do tasks at the lowest possible cost while also taking into consideration travel time and distance. The term "minimum spanning tree" refers to the spanning tree that has a weight that is less than or equal to the weight of all other feasible spanning trees. A spanning tree is created when every vertex in a network is linked and has no cycles in it; there must be no other spanning tree with a lesser weight. The minimum spanning tree problem has been solved using a variety of methods that have been published in the literature. They provide the best answer to the minimum spanning tree problems given an undirected graph using Prim's and Kruskal's algorithms. A probabilistic method for resolving computational issues that may be simplified to finding the best route via graphs is the Ant Colony Optimization Algorithm (ACOA). This algorithm has been developed based on how ants search for a route between their nest and a food source while foraging. This paper proposes a novel technique and effective method for studying the large scale of the problem and determining the minimum cost-spanning tree of a connected weight undirected graph with fewer iterations using the Modified Ant Colony Optimization Algorithm (ACOA). When the graph has a large number of nodes, this novel approach is simpler and easier to implement than other existing algorithms, and by comparing our methods to Prim's and Kruskal's, we can get the same results.
VL  - 10
IS  - 6
ER  -

Copy | Download