Edge Reduction Algorithm: An Efficient Approach to Minimum Spanning Trees in Sparse Graphs

Edge Reduction Algorithm: An Efficient Approach to Minimum Spanning Trees in Sparse Graphs

Pratham Katariya1, Atharva Salve2, Neha Kadam3, Kasturi Naware4, Gauri Ghule5

Department of Electronics and Telecommunication Engineering,

Vishwakarma Institute of Information Technology Pune,

Maharashtra, INDIA,

ABSTRACT

Minimum spanning trees (MST's) play an important role in network optimization. Many algorithms have been designed and developed for computing efficient MST's of general graphs. However, it has become increasingly apparent with the need for very large sparse graphs in many applications. In this paper, a new edge reduction algorithm to build MST's for sparse graphs is proposed. Such graph properties make our approach provide more time complexities than its corresponding traditional counterparts to ensure high-quality practical performances. We proceed to test with high intensity on multiple datasets to illustrate the performance improvements with regard to traditional techniques up to a 3-fold gain for Kruskal on sparse graphs. It is very promising in large-scale network design and optimization problems in telecommunication, transport, and bio-informatics.