Optimizing Minimum Spanning Tree Computation:...

Optimizing Minimum Spanning Tree Computation: An Artificial Neural Network Approach for Enhanced Efficiency in Graph Theory

Author Name : Uday Vallabhaneni , Praneeth Venkata Sai Eluri , Bhanu Teja Nimmagadda , Tavva Chiranjeevi Naga Anish , Bharath Chidipothu , Damarla Bhuvan Sri Sai

ABSTRACT In this research paper, we introduce a novel approach to tackle the Minimum Spanning Tree (MST) problem using Artificial Neural Networks (ANNs). The MST problem is a fundamental challenge within graph theory, holding significant real-world applications. Traditional algorithms for MST problem-solving often demand substantial computational resources and memory usage. Our proposed approach aims to mitigate these limitations by harnessing the capabilities of ANNs, which have demonstrated efficacy in solving a variety of optimization problems. Our ANN-based methodology revolves around training a neural network to predict the edges of the MST for a given input graph. This training involves a dataset of input graphs and their corresponding MSTs. We also introduce a unique loss function that simultaneously considers the accuracy of the predicted MST and the computational efficiency of the neural network. To assess the effectiveness of our approach, we conduct extensive evaluations on diverse benchmark datasets and compare our results with those of state-of-the-art MST algorithms. The experimental outcomes demonstrate that our ANN-based approach yields comparable or superior results to existing algorithms, all the while significantly improving computation time and memory utilization. In summary, our proposed methodology offers a promising solution to the MST problem using ANNs and exhibits potential for extension to other optimization challenges within graph theory