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.
This work has been partially supported by the IST Programme of the EU under contract n. IST-1999-14186 (ALCOM-FT), by the
Italian Ministry of University and Scientific Research (Project “Algorithms for Large Data Sets: Science and Engineering”)
and by CNR, the Italian National Research Council, under contract n. 01.00690.CT26.