{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,10]],"date-time":"2025-05-10T15:44:25Z","timestamp":1746891865985,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540439776"},{"type":"electronic","value":"9783540456438"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45643-0_9","type":"book-chapter","created":{"date-parts":[[2007,9,25]],"date-time":"2007-09-25T00:58:33Z","timestamp":1190681913000},"page":"111-125","source":"Crossref","is-referenced-by-count":7,"title":["Maintaining Dynamic Minimum Spanning Trees: An Experimental Study"],"prefix":"10.1007","author":[{"given":"Giuseppe","family":"Cattaneo","sequence":"first","affiliation":[]},{"given":"Pompeo","family":"Faruolo","sequence":"additional","affiliation":[]},{"given":"Umberto Ferraro","family":"Petrillo","sequence":"additional","affiliation":[]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,7,12]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"D. Alberts, G. Cattaneo, G. F. Italiano, \u201cAn empirical study of dynamic graph algorithms\u201d, ACM Journal on Experimental Algorithmics, vol. 2 (1997).","DOI":"10.1145\/264216.264223"},{"key":"9_CR2","unstructured":"D. Alberts, G. Cattaneo, G. F. Italiano, U. Nanni, C. D. Zaroliagis \u201cA Software Library of Dynamic Graph Algorithms\u201d. Proc. Algorithms and Experiments (ALEX 98), Trento, Italy, February 9\u201311, 1998, R. Battiti and A. A. Bertossi (Eds), pp. 129\u2013136."},{"key":"9_CR3","unstructured":"D. Alberts, M. R. Henzinger, \u201cAverage Case Analysis of Dynamic Graph Algorithms\u201d, Proc. 6th Symp. on Discrete Algorithms (1995), 312\u2013321."},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"C.R. Aragon, R. Seidel, \u201cRandomized search trees\u201d, Proc. 30th Annual Symp. on Foundations of Computer Science (FOCS 89), 1989, pp. 540\u2013545.","DOI":"10.1109\/SFCS.1989.63531"},{"key":"9_CR5","unstructured":"G. Amato, G. Cattaneo, G. F. Italiano, \u201cExperimental Analysis of Dynamic Minimum Spanning Tree Algorithms\u201d, Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms, (1997), 5\u20137."},{"key":"9_CR6","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s. Random Graphs. Academic Press, London, 1985."},{"key":"9_CR7","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduction to Algorithms. Mac-Graw Hill, NY, 1990."},{"key":"9_CR8","series-title":"Lect Notes Comput Sci","volume-title":"Procs. 3rd Workshop on Algorithm Engineering (WAE2000)","author":"C. Demetrescu","year":"2001","unstructured":"C. Demetrescu, D. Frigioni, A. Marchetti-Spaccamela, U. Nanni. \u201cMaintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study.\u201d Procs. 3rd Workshop on Algorithm Engineering (WAE2000). Lecture Notes in Computer Science, Springer-Verlag, 2001."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"C. Demetrescu and G.F. Italiano. Fully dynamic transitive closure: Breaking through the O(n2) barrier. Proc. of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201900), pages 381\u2013389, 2000.","DOI":"10.1109\/SFCS.2000.892126"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"C. Demetrescu, G. F. Italiano, \u201cFully Dynamic All Pairs Shortest Paths with Real Edge Weights\u201d. Proc. 42nd IEEE Annual Symp. on Foundations of Computer Science (FOCS 2001), Las Vegas, NV, U.S.A., October 14\u201317, 2001.","DOI":"10.1109\/SFCS.2001.959900"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano and A. Nissenzweig, \u201cSparsification \u2014 A technique for speeding up dynamic graph algorithms.\u201d. In Journal of ACM, Vol. 44, 1997, pp. 669\u2013696.","journal-title":"Journal of ACM"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, T. H. Spencer, \u201cSeparator based sparsification for dynamic planar graph algorithms\u201d, Proc. 25th ACM Symposium on Theory of Computing (1993), 208\u2013217.","DOI":"10.1145\/167088.167159"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung, Maintenance of a minimum spanning forest in a dynamic plane graph, J. Algorithms, 13:33\u201354, 1992.","journal-title":"J. Algorithms"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"G.N. Frederickson, \u201cData structures for on-line updating of minimum spanning trees, with applications\u201d, SIAM J. Comput. 14 (1985), 781\u2013798.","journal-title":"SIAM J. Comput."},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \u201cAmbivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees\u201d, Proc. 32nd IEEE Symp. Foundations of Computer Science (1991), 632\u2013641.","DOI":"10.1109\/SFCS.1991.185429"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"D. Frigioni, M. Ioffreda, U. Nanni, G. Pasqualone. \u201cExperimental Analysis of Dynamic Algorithms for the Single Source Shortest Path Problem.\u201d ACM Journal on Experimental Algorithmics, vol. 3 (1998), Article 5.","DOI":"10.1145\/297096.297147"},{"key":"9_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/3-540-68530-8_31","volume-title":"Proc. 6th European Symp. on Algorithms","author":"D. Frigioni","year":"1998","unstructured":"D. Frigioni, T. Miller, U. Nanni, G. Pasqualone, G. Schaefer, and C. Zaroliagis \u201cAn experimental study of dynamic algorithms for directed graphs\u201d, in Proc. 6th European Symp. on Algorithms, Lecture Notes in Computer Science 1461 (Springer-Verlag, 1998), pp. 368\u2013380."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"M. R. Henzinger and V. King, Randomized dynamic graph algorithms with polylogarithmic time per operation, Proc. 27th Symp. on Theory of Computing, 1995, 519\u2013527.","DOI":"10.1145\/225058.225269"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"M. R. Henzinger and V. King, Fully dynamic biconnectivity and transitive closure, Proc. 36th IEEE Symp. Foundations of Computer Science, pages 664\u2013672, 1995.","DOI":"10.1109\/SFCS.1995.492668"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"M. R. Henzinger and V. King, Maintainig minimum spanning trees in dynamic graphs, Proc. 24th Int. Coll. Automata, Languages and Programming (ICALP 97), pages 594\u2013604, 1997.","DOI":"10.1007\/3-540-63165-8_214"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"J. Holm, K. de Lichtenberg, and M. Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Proc. 30th Symp. on Theory of Computing (1998), pp. 79\u201389.","DOI":"10.1145\/276698.276715"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"R. Iyer, D. R. Karger, H. S. Rahul, and M. Thorup, An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms, Proc. Workshop on Algorithm Engineering and Experimentation, 2000.","DOI":"10.1145\/945394.945398"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"V. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS\u201999), 1999.","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"V. King and G. Sagert. A fully dynamic algorithm for maintaining the transitive closure. Proc. 31st ACM Symposium on Theory of Computing (STOC\u201999), pages 492\u2013498, 1999.","DOI":"10.1145\/301250.301380"},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"48","DOI":"10.2307\/2033241","volume":"7","author":"J. B. Kruskal","year":"1956","unstructured":"J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc. 7, (1956), 48\u201350.","journal-title":"Proc. Amer. Math. Soc."},{"issue":"1","key":"9_CR26","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/204865.204889","volume":"38","author":"K. Melhorn","year":"1995","unstructured":"K. Melhorn and S. N\u00e4her, \u201cLEDA, A platform for combinatorial and geometric computing\u201d. Comm. ACM, (1995), 38(1): pp. 96\u2013102.","journal-title":"Comm. ACM"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"M. Rauch, \u201cImproved data structures for fully dynamic biconnectivity\u201d, Proc. 26th Symp. on Theory of Computing (1994), 686\u2013695.","DOI":"10.1145\/195058.195434"},{"key":"9_CR28","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"24","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees, J. Comp. Syst. Sci., 24:362\u2013381, 1983.","journal-title":"J. Comp. Syst. Sci."},{"key":"9_CR29","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R. E. Tarjan","year":"1984","unstructured":"R. E. Tarjan and J. van Leeuwen, Worst-case analysis of set union algorithms, J. Assoc. Comput. Mach., 31:245\u2013281, 1984.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering and Experiments"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45643-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:20:38Z","timestamp":1737436838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45643-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540439776","9783540456438"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-45643-0_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}