Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights

1. Amato, G., Cattaneo, G., Italiano, G.F.: Experimental analysis of dynamic minimum spanning tree algorithms (extended abstract). In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 314–323. New Orleans (1997)

   Google Scholar 

2. Buriol, L.S., Resende, M.G.C., Ribeiro, C.C., Thorup, M.: A memetic algorithm for OSPF routing. In: Proceedings of the 6th INFORMS Telecom, pp. 187–188. Boca Raton (2002)

   Google Scholar 

3. Buriol, L.S., Resende, M.G.C., Ribeiro, C.C., Thorup, M.: A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks 46, 36–56 (2005)

   Article  MATH  MathSciNet  Google Scholar 

4. Buriol, L.S., Resende, M.G.C., Thorup, M.: Speeding up shortest path algorithms. Technical Report TD-5RJ8B, AT&T Labs Research (September 2003)

   Google Scholar 

5. Cattaneo, G., Faruolo, P., Ferraro-Petrillo, U., Italiano, G.F.: Maintaining dynamic minimum spanning trees: An experimental study. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 111–125. Springer, Heidelberg (2002)

   Google Scholar 

6. Demetrescu, C., Goldberg, A., Johnson, D.: Ninth DIMACS implementation challenge – shortest paths (2006), On-line reference at http://www.dis.uniroma1.it/c̃hallenge9/ , last visited in June 23

7. Eppstein, D., Galil, Z., Italiano, G.F., Nissemzweig, A.: Sparsification – A technique for speeding up dynamic graph algorithms. Journal of the ACM 44, 669–696 (1997)

   Article  MATH  MathSciNet  Google Scholar 

8. Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing 14, 781–798 (1985)

   Article  MATH  MathSciNet  Google Scholar 

9. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pp. 632–641. San Juan (1991)

   Google Scholar 

10. Henzinger, M.H., King, V.: Maintaining minimum spanning trees in dynamic graphs. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 594–604. Springer, Heidelberg (1997)

    Google Scholar 

11. Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 79–89. ACM Press, New York (1998)

    Google Scholar 

12. Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society 7, 48–50 (1956)

    Article  MathSciNet  Google Scholar 

13. Prim, R.C.: Shortest connection networks and some generalizations. Bell Systems Technical Journal 36, 1389–1401 (1957)

    Google Scholar 

14. Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM 33, 668–676 (1990)

    Article  Google Scholar 

15. Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. Journal of Computer and System Sciences 26, 362–391 (1983)

    Article  MATH  MathSciNet  Google Scholar 

16. Spira, P.M., Pan, A.: On finding and updating spanning trees and shortest paths. SIAM Journal on Computing 4, 375–380 (1975)

    Article  MATH  MathSciNet  Google Scholar 

17. Werneck, R.F., Tarjan, R.E.: Self-adjusting top trees. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 813–822. Vancouver (2005)

    Google Scholar 

18. Zaroliagis, C.D.: Implementations and experimental studies of dynamic graph algorithms. In: Fleischer, R., Moret, B.M.E., Schmidt, E.M. (eds.) Experimental Algorithmics. LNCS, vol. 2547, pp. 229–278. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

Download references