An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem

This paper details the design, implementation, and testing of a one edge pass non-greedy algorithm for the minimum spanning tree problem. The use of network labeling procedures and path weights to screen entering edges, provides a novel implementation of this algorithm. The choice of data structures also allows for an efficient implementation of reoptimization procedures, which have hitherto never been studied. Comprehensive results on the performance of both the greedy and non-greedy algorithms in optimization and reoptimization modes under various screening criteria, graph topologies, sizes and densities, and weight distributions are presented. The empirical results based on 855 problems bear out Tarjan’s conjecture that greedy algorithms have a competitive advantage over non-greedy algorithms for the minimum spanning tree problem, except in special cases. However, for the problems tested, when a small percentage of edge weights are changed, non-greedy approaches are competitive with greedy algorithms in reoptimization mode.