ALCOMFT-TR-02-99

Giuseppe Cattaneo, Pompeo Faruolo, Umberto Ferraro-Petrillo and Giuseppe F. Italiano
Maintaining Dynamic Minimum Spanning Trees: An Experimental Study
Rome. Work package 5. May 2002.

Abstract: We report our findings on an extensive empirical study on several algorithms for maintaining minimum spanning trees in dynamic graphs. In particular, we have implemented and tested a variant of the polylogarithmic algorithm by Holm et al., sparsification on top of Frederickson's algorithm, and compared them to other (less sophisticated) dynamic algorithms. In our experiments, we considered as test sets several random, semi-random and worst-case inputs previously considered in the literature.

Postscript file: ALCOMFT-TR-02-99.ps.gz (614 kb).