{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:32:53Z","timestamp":1794357173422,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":18,"publisher":"Springer US","isbn-type":[{"value":"9780387307701","type":"print"},{"value":"9780387301624","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_153","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:35:59Z","timestamp":1214490959000},"page":"332-335","source":"Crossref","is-referenced-by-count":0,"title":["Fully Dynamic Connectivity: Upper and Lower Bounds"],"prefix":"10.1007","author":[{"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"153_CR1_153","doi-asserted-by":"crossref","unstructured":"Alberts, D., Cattaneo, G., Italiano, G.F.: An empirical study of dynamic graph algorithms. ACM J.\u00a0Exp. Algorithmics 2 (1997)","DOI":"10.1145\/264216.264223"},{"issue":"1","key":"153_CR2_153","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J.\u00a0Comp. Syst. Sci. 65(1), 38\u201372 (2002)","journal-title":"J. Comp. Syst. Sci."},{"issue":"3","key":"153_CR3_153","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0020-0190(97)00056-2","volume":"62","author":"D. Eppstein","year":"1997","unstructured":"Eppstein, D.: Dynamic Connectivity in Digital Images. Inf. Process. Lett. 62(3), 121\u2013126 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"153_CR4_153","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., Nissenzweig, A.: Sparsification\u00a0\u2013 a\u00a0technique for speeding up dynamic graph algorithms. J.\u00a0Assoc. Comp. Mach. 44(5), 669\u2013696 (1997)","journal-title":"J. Assoc. Comp. Mach."},{"key":"153_CR5_153","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Italiano, G.F., Tamassia, R., Tarjan, R.E., Westbrook, J., Yung, M.: Maintenance of a\u00a0minimum spanning forest in a\u00a0dynamic plane graph. J.\u00a0Algorithms 13, 33\u201354 (1992)","journal-title":"J. Algorithms"},{"key":"153_CR6_153","doi-asserted-by":"crossref","unstructured":"Eyal, E., Halperin, D.: Improved Maintenance of Molecular Surfaces Using Dynamic Graph Connectivity. in: Proc. 5th International Workshop on Algorithms in Bioinformatics (WABI 2005), Mallorca, Spain, 2005, pp.\u00a0401\u2013413","DOI":"10.1007\/11557067_33"},{"key":"153_CR7_153","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. SIAM J.\u00a0Comp. 14, 781\u2013798 (1985)","journal-title":"SIAM J. Comp."},{"issue":"2","key":"153_CR8_153","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/S0097539792226825","volume":"26","author":"G.N. Frederickson","year":"1997","unstructured":"Frederickson, G.N.: Ambivalent data structures for dynamic 2\u2010edge\u2010connectivity and k smallest spanning trees. In: Proc. 32nd Symp. Foundations of Computer Science, 1991, pp.\u00a0632\u2013641","journal-title":"SIAM J. Comput."},{"issue":"3","key":"153_CR9_153","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/PL00009228","volume":"22","author":"M.R. Henzinger","year":"1998","unstructured":"Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351\u2013362 (1998)","journal-title":"Algorithmica"},{"issue":"4","key":"153_CR10_153","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"M.R. Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J.\u00a0ACM 46(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"key":"153_CR11_153","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de\u00a0Lichtenberg, K., Thorup, M.: Poly\u2010logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J.\u00a0ACM 48, 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"153_CR12_153","doi-asserted-by":"crossref","unstructured":"Iyer, R., Karger, D., Rahul, H., Thorup, M.: An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms. ACM J.\u00a0Exp. Algorithmics 6 (2001)","DOI":"10.1145\/945394.945398"},{"key":"153_CR13_153","unstructured":"Miltersen, P.B.: Cell probe complexity\u00a0\u2013 a\u00a0survey. In: 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Advances in Data Structures Workshop, 1999"},{"key":"153_CR14_153","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity models for incremental computation. In: Ausiello, G., Italiano, G.F. (eds.) Special Issue on Dynamic and On-line Algorithms. Theor. Comp. Sci. 130(1), 203\u2013236 (1994)","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"153_CR15_153","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Demain, E.D.: Lower Bounds for Dynamic Connectivity. In: Proc. 36th ACM Symposium on Theory of Computing (STOC), 2004, pp. 546\u2013553","DOI":"10.1145\/1007352.1007435"},{"key":"153_CR16_153","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Tarni\u0163\u01ce, C.: On Dynamic Bit-Probe Complexity, Theoretical Computer Science, Special Issue on ICALP'05. In: Italiano, G.F., Palamidessi, C. (eds.) vol.\u00a0380, pp.\u00a0127\u2013142 (2007) A\u00a0preliminary version in Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), 2005, pp. 969\u2013981","DOI":"10.1007\/11523468_78"},{"key":"153_CR17_153","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM J. Comp. 14, 862\u2013874 (1985)","journal-title":"SIAM J. Comp."},{"key":"153_CR18_153","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343\u2013350","DOI":"10.1145\/335305.335345"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T22:15:04Z","timestamp":1662156904000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_153"}},"subtitle":["2000; Thorup"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_153","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2008]]}}}