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.
Maintaining Minimum Spanning Tree on Dynamic Graphs: An experimental study / G., Cattaneo; P., Faruolo; FERRARO PETRILLO, Umberto; G. F., Italiano. - STAMPA. - 2049 Sono presenti su Scopus delle citazioni al prodotto reperibili attraverso la query REF("Maintaining dynamic minimum spanning trees: An experimental study"):(2002), pp. 111-125. (Intervento presentato al convegno Workshop on Algorithm Engineering and Experiments tenutosi a San Francisco, USA nel 6--8 Gennaio 2002) [10.1007/3-540-45643-0_9].
Maintaining Minimum Spanning Tree on Dynamic Graphs: An experimental study
FERRARO PETRILLO, UMBERTO;
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
