6533b7ddfe1ef96bd1273dc9
RESEARCH PRODUCT
Maintaining Dynamic Minimum Spanning Trees: An Experimental Study
U. Ferraro PetrilloPompeo FaruoloGiuseppe CattaneoGiuseppe F. Italianosubject
Random graphSpanning treeExperimental analysisMinimum spanning tree algorithmsbusiness.industryApplied MathematicsExperimental analysis; Minimum spanning tree algorithms; Dynamic graphsMinimum spanning treeGraphDistributed minimum spanning treedynamic graphs; experimental analysis; minimum spanning tree algorithmsEmpirical researchDynamic problemDiscrete Mathematics and CombinatoricsThe InternetbusinessSettore ING-INF/05 - Sistemi di Elaborazione delle InformazioniAlgorithmMathematicsDynamic graphsdescription
AbstractWe 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).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-03-01 |