Experimental analysis of dynamic minimum spanning tree algorithms

Abstract

We conduct an extensive empirical study on the performance of several algorithms for maintaining the minimum spanning tree of a dynamic graph. In particular, we implemented and tested Frederickson`s algorithms, and sparsification on top of Frederickson`s algorithms, and compared them to other dynamic algorithms. Moreover, we propose a variant of a dynamic algorithm by Frederickson, which was in our experience always faster than the other implementations derived from the papers. In our experiments, we considered both random and non-random inputs, with non-random inputs trying to enforce bad update patterns on the algorithms. For random inputs, a simple adaptation of a partially dynamic data structure on Kruskal`s algorithm was the fastest implementation. For non-random inputs, sparsification yielded the fastest algorithm. In both cases, the performance of our variant of the algorithm of Frederickson was close to that of the fastest algorithm.