Rural Electrification of Selected Areas in the Northern Region of Ghana Viewed as a Minimum Spanning Tree Problem
Abstract
The minimum spanning tree problem usually finds a spanning tree with the least total weight in a connected undirected graph. Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids. In this study, the concept of Minimum Spanning Tree Problem has been successfully used to analyze rural electrification of selected areas in the Savelugu Municipality and Mion Districts in the Northern Region of Ghana. Secondary data was collected from Northern Electricity Distribution Company (NEDCO) in Tamale, Ghana. Networks of the selected areas in the Savelugu and Mion Districts in the Northern Region of Ghana were constructed. Kruskal’s algorithm has been employed to obtain the optimal electrification routes for the selected areas and Management Scientist Version 5 software used to confirm the optimal solutions. Post-optimality analysis has also been conducted to determine how variations of the distances between villages in the considered cases studies affect the optimal lengths of electrification routes. The government of Ghana should use the determined optimal routes as a guide to minimize the total cost of cables for future electrification of the selected areas. Other countries should apply techniques like the Kruskal’s algorithm to minimize the cost of cables involved in their electrification processes.
References
Ghana Country Commercial Guide. (2022, July 22). International Trade Administration. https://segensolar.co.za/ghana/
Chang, R-S., & Leu, S-J. (1997). The minimum labeling spanning trees. Information Processing Letters, 63(5), 277-282. https://doi.org/10.1016/S0020-0190(97)00127-0
Graham, R. L., & Hell, P. (1985). On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1), 43-57. https://doi.org/10.1109/MAHC.1985.10011
Dixon, B., Rauch, M., & Tarjan, R. E. (1990). Verification and sensitivity analysis of minimum spanning tree in linear time. SIAM Journal on Computing, 21(6), 1184-1192. https://doi.org/10.1137/0221070
Chazelle, B. (2000). A minimum spanning tree algorithm with inverse-Ackermann type complexity. Journal of the ACM, 47(6), 1028-1047. https://doi.org/10.1145/355541.355562
Jayawant, P., & Glavin, K. V. (2009). Minimum spanning trees. Involve : A Journal of Mathematics, 4(4), 439-450. https://doi.org/10.2140/involve.2009.2.439
Hassan, M. R. (2011). An efficient method to solve least-cost minimum spanning tree (LC-MST) problem. Journal of King Saud University - Computer and Information Sciences, 24, 101-105. https://doi.org/10.1016/j.jksuci.2011.12.001
Mandal, A., Dutta, J., & Pal, S. C. (2012). A new efficient technique to construct a minimum spanning tree. International Journal of Advanced Research in Computer Science and Software Engineering, 2(10), 93-97.
Vijayalakshmir, D., & Kalaivani, R. (2014). Minimum cost spanning tree using matrix algorithm. International Journal of Scientific and Research Publications, 4(9), 1-5.
Le, P., Nguyen, T. D., & Bektas, T. (2016). Generalized minimum spanning tree games. EURO Journal on Computational Optimization, 4(2), 167-188. https://doi.org/10.1007/s13675-015-0042-y
Kataoka, S., & Yamada, T. (2016). Algorithms for the minimum spanning tree problem with resource allocation, Operations Research Perspective, 3, 5-13. https://doi.org/10.1016/j.orp.2015.12.001
Biswas, P., Goel, M., Negi, H., & Datta, M. (2016). An efficient greedy minimum spanning tree algorithm based on vertex associative cycle detection method. Procedia Computer Science, 92, 513-519. https://doi.org/10.1016/j.procs.2016.07.376
Effanga, E. O., & Edeke, U. E. (2016). Minimum spanning tree of city-to-city road network in Nigeria. IOSR Journal of Mathematics (IOSR-JM), 12(4), 41-45. https://doi.org/10.9790/5728-1204054145
Shrestha, A., Jha, S. K., Shah, B., & Gautam, B. R. (2016). Optimal grid network for rural electrification of Upper Karnali Hydro Project affected area. IEEE Region 10 Humanitarian Technology Conference (R10-HTC), 1-5. https://doi.org/10.1109/R10-HTC.2016.7906799
Nolan, S., Strachan, S., Rakhra, P., & Frame, D. (2017). Optimised network planning of mini-grids for the electrification of developing countries. IEEE PES-IAS PowerAfrica, 489-494. https://doi.org/10.1109/PowerAfrica.2017.7991274
Saxena, S. & Urooj (2018). New approaches for minimum spanning tree. International Journal of Advanced Research in Science and Engineering, 7(3), 353-360.
Chreang, S., & Kumhom, P. (2018). A method of selecting cable configuration for microgrid using minimum spanning tree. International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology, 489-492. https://doi.org/10.1109/ECTICon.2018.8620055
Delfiya, G., & Lancy, A.A. (2019). Spanning tree and minimum spanning tree. International Journal of Scientific Development and Research (IJSDR), 4(3), 146-150.
Shivaani, K., & Kanna, K. N. (2020). Performance analysis of minimum spanning tree algorithms. International Journal of Computer Engineering and Technology (IJCET), 11(5), 17-28.
Sahu, D. N., & Panda, M. (2021). Study of minimum spanning tree in graph isomorphism using efficient algorithm. International Journal for Innovative Research in Multidisciplinary Field, 7(8), 159-164.
Sahu, D. N. (2021). Study of minimum spanning tree implementation on travelling salesman problem based on complexities of algorithm. Journal of Emerging Technologies and Innovative Research (JETIR), 8(8), 882-891.
Tuffaha, I. R., & Almaktoom, A. (2021). Using minimum spanning tree to reduce cost of the cable for the internet. PalArch’s Journal of Archaeology of Egypt, 18(15), 215-223.
Niluminda, K. P. O., & Ekanayake, E. M. U. S. B. (2020). Innovative matrix algorithm to address the minimal cost spanning tree problem. Journal of Electrical Electronics Engineering, 1(1), 148-153.
Niluminda, K. P. O., & Ekanayake, E. M. U. S. B. (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.
Wang, X., Li, S., Hou, C., & Zhang, G. (2023), Minimum spanning tree method for sparse graphs. Mathematical Problems in Engineering, 2023, 1-6. https://doi.org/10.1155/2023/8591115
Cayley, A. (1889). A theorem on trees. Quarterly Journal of Pure and Applied Mathematics, 23, 376-378.
Henn, S. T. (2007). Weight-Constrained Minimum Spanning Tree Problem. Diploma Thesis, Department of Mathematics, University of Kaiserslautern.
Anderson, D. R., Sweeney, D. J., & Williams, T. A. (2000). Management Scientist, Version 5.
This work is licensed under a Creative Commons Attribution 4.0 International License.
.jpg){kind=logo}
