{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:50:00Z","timestamp":1773481800732,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540728443","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72845-0_30","type":"book-chapter","created":{"date-parts":[[2007,6,26]],"date-time":"2007-06-26T12:51:37Z","timestamp":1182862297000},"page":"393-405","source":"Crossref","is-referenced-by-count":6,"title":["Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights"],"prefix":"10.1007","author":[{"given":"Celso C.","family":"Ribeiro","sequence":"first","affiliation":[]},{"given":"Rodrigo F.","family":"Toso","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","unstructured":"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\u2013323. New Orleans (1997)"},{"key":"30_CR2","unstructured":"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\u2013188. Boca Raton (2002)"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1002\/net.20070","volume":"46","author":"L.S. Buriol","year":"2005","unstructured":"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\u00a046, 36\u201356 (2005)","journal-title":"Networks"},{"key":"30_CR4","unstructured":"Buriol, L.S., Resende, M.G.C., Thorup, M.: Speeding up shortest path algorithms. Technical Report TD-5RJ8B, AT&T Labs Research (September 2003)"},{"key":"30_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-45643-0_9","volume-title":"Algorithm Engineering and Experiments","author":"G. Cattaneo","year":"2002","unstructured":"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.\u00a02409, pp. 111\u2013125. Springer, Heidelberg (2002)"},{"key":"30_CR6","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D.: Ninth DIMACS implementation challenge \u2013 shortest paths (2006), On-line reference at \n                    \n                      http:\/\/www.dis.uniroma1.it\/c\u0303hallenge9\/\n                    \n                    \n                  , last visited in June 23"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Nissemzweig, A.: Sparsification \u2013 A technique for speeding up dynamic graph algorithms. Journal of the ACM\u00a044, 669\u2013696 (1997)","journal-title":"Journal of the ACM"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing\u00a014, 781\u2013798 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013641. San Juan (1991)","DOI":"10.1109\/SFCS.1991.185429"},{"key":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1007\/3-540-63165-8_214","volume-title":"Automata, Languages and Programming","author":"M.H. Henzinger","year":"1997","unstructured":"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.\u00a01256, pp. 594\u2013604. Springer, Heidelberg (1997)"},{"key":"30_CR11","first-page":"79","volume-title":"Proceedings of the 30th ACM Symposium on Theory of Computing","author":"J. Holm","year":"1998","unstructured":"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\u201389. ACM Press, New York (1998)"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"48","DOI":"10.2307\/2033241","volume":"7","author":"J.B. Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society\u00a07, 48\u201350 (1956)","journal-title":"Proc. of the American Mathematical Society"},{"key":"30_CR13","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R.C. Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Systems Technical Journal\u00a036, 1389\u20131401 (1957)","journal-title":"Bell Systems Technical Journal"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM 33, 668\u2013676 (1990)","journal-title":"Communications of the ACM"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. Journal of Computer and System Sciences\u00a026, 362\u2013391 (1983)","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0204032","volume":"4","author":"P.M. Spira","year":"1975","unstructured":"Spira, P.M., Pan, A.: On finding and updating spanning trees and shortest paths. SIAM Journal on Computing\u00a04, 375\u2013380 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR17","unstructured":"Werneck, R.F., Tarjan, R.E.: Self-adjusting top trees. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 813\u2013822. Vancouver (2005)"},{"key":"30_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/3-540-36383-1_11","volume-title":"Experimental Algorithmics","author":"C.D. Zaroliagis","year":"2002","unstructured":"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.\u00a02547, pp. 229\u2013278. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72845-0_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:49:06Z","timestamp":1619516946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72845-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540728443"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72845-0_30","relation":{},"subject":[]}}