Experimental Analysis of Dynamic Minimum Spanning Tree Algorithms (Extended Abstract).
Giuseppe M. Amato, Giuseppe Cattaneo, Giuseppe Francesco Italiano · 1997
) Giuseppe Amato Giuseppe Cattaneo y Giuseppe F. Italiano z 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 clos...