IRIS - Institutional Research Information System
IRIS è il sistema di gestione integrata dei dati della ricerca adottato dalla Luiss Guido Carli. Il Catalogo dei prodotti della ricerca della Luiss raccoglie e rende disponibile, dove possibile nel rispetto del diritto d'autore, la produzione scientifica dei docenti e ricercatori dell'Ateneo. Il Catalogo alimenta inoltre i siti docenti del MIUR.
EnglishWe 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).
| Titolo: | Maintaining Dynamic Minimum Spanning Trees: An Experimental Study | |
| Autori: | ||
| Data di pubblicazione: | 2010 | |
| Rivista: | ||
| Handle: | http://hdl.handle.net/11385/199797 | |
| Appare nelle tipologie: | 01.1 - Articolo su rivista (Article) |
File in questo prodotto:
Pubblicazioni consigliate
Copyright © 2021