Maintaining Dynamic Minimum Spanning Trees: An Experimental Study

摘要

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 Pred-erickson'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.