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

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.