We report our findings on an extensive empirical study on the performance of several algorithms for maintaining minimum spanning trees in dynamic graphs. In particular, we have implemented and tested several variants of the polylogarithmic algorithm by Holm et al, sparsification on top of Frederickson's algorithm, and 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 together with inputs arising from real-world applications (e.g., a graph of the Internet Autonomous Systems). (C) 2009 Elsevier B.V. All rights reserved.

Maintaining dynamic minimum spanning trees: An experimental study / G., Cattaneo; P., Faruolo; FERRARO PETRILLO, Umberto; G. F., Italiano. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 158:5(2010), pp. 404-425. [10.1016/j.dam.2009.10.005]

Maintaining dynamic minimum spanning trees: An experimental study

FERRARO PETRILLO, UMBERTO;
2010

Abstract

We report our findings on an extensive empirical study on the performance of several algorithms for maintaining minimum spanning trees in dynamic graphs. In particular, we have implemented and tested several variants of the polylogarithmic algorithm by Holm et al, sparsification on top of Frederickson's algorithm, and 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 together with inputs arising from real-world applications (e.g., a graph of the Internet Autonomous Systems). (C) 2009 Elsevier B.V. All rights reserved.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/145404
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 9
social impact