{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:43:48Z","timestamp":1792111428259,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":18,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_153","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:51:54Z","timestamp":1553097114000},"page":"793-797","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","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","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"153_CR6310","doi-asserted-by":"crossref","unstructured":"Alberts D, Cattaneo G, Italiano GF (1997) Anempirical study of dynamic graph algorithms. ACM J Exp Algorithms 2","DOI":"10.1145\/264216.264223"},{"issue":"1","key":"153_CR6311","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P Beame","year":"2002","unstructured":"Beame P, Fich FE (2002) Optimal bounds for the predecessor problem and related problems. J Comput Syst Sci 65(1):38\u201372","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"153_CR6312","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 (1997) Dynamic connectivity in digital images. Inf Process Lett 62(3):121\u2013126","journal-title":"Inf Process Lett"},{"issue":"5","key":"153_CR6313","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 GF, Nissenzweig A (1997) Sparsification \u2013 a technique for speeding up dynamic graph algorithms. J Assoc Comput Mach 44(5):669\u2013696","journal-title":"J Assoc Comput Mach"},{"key":"153_CR6314","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 GF, Tamassia R, Tarjan RE, Westbrook J, Yung M (1992) Maintenance of a minimum spanning forest in a dynamic plane graph. J Algorithms 13:33\u201354","journal-title":"J Algorithms"},{"key":"153_CR6315","doi-asserted-by":"crossref","unstructured":"Eyal E, Halperin D (2005) Improved maintenance of molecular surfacesusing dynamic graph connectivity. In: Proceedings of the 5th international workshop on algorithms in bioinformatics (WABI 2005), Mallorca, pp 401\u2013413","DOI":"10.1007\/11557067_33"},{"key":"153_CR6316","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"GN Frederickson","year":"1985","unstructured":"Frederickson GN (1985) Data structures for on-line updating of minimum spanning trees. SIAM J Comput 14:781\u2013798","journal-title":"SIAM J Comput"},{"key":"153_CR6317","doi-asserted-by":"crossref","unstructured":"Frederickson GN (1991) Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In: Proceedings of the 32nd symposium on foundations of computer science, pp 632\u2013641","DOI":"10.1109\/SFCS.1991.185429"},{"issue":"3","key":"153_CR6318","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/PL00009228","volume":"22","author":"MR Henzinger","year":"1998","unstructured":"Henzinger MR, Fredman ML (1998) Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3):351\u2013362","journal-title":"Algorithmica"},{"issue":"4","key":"153_CR6319","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"MR Henzinger","year":"1999","unstructured":"Henzinger MR, King V (1999) Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J ACM 46(4):502\u2013516","journal-title":"J ACM"},{"key":"153_CR6320","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm J, de Lichtenberg K, Thorup M (2001) Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J ACM 48:723\u2013760","journal-title":"J ACM"},{"key":"153_CR6321","doi-asserted-by":"crossref","unstructured":"Iyer R, Karger D, Rahul H, Thorup M (2001) An experimental study of polylogarithmic, fully dynamic, connectivity algorithms. ACM J Exp Algorithmics 6","DOI":"10.1145\/945394.945398"},{"key":"153_CR6322","unstructured":"Miltersen PB (1999) Cell probe complexity \u2013 a survey. In: 19th conference on the foundations of software technology and theoretical computer science (FSTTCS). Advances in Data Structures Workshop"},{"key":"153_CR6323","doi-asserted-by":"crossref","unstructured":"Miltersen PB, Subramanian S, Vitter JS, Tamassia R (1994) Complexity models for incremental computation. In: Ausiello G, Italiano GF (eds) Special issue on dynamic and on-line algorithms. Theor Comput Sci 130(1):203\u2013236","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"153_CR6324","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu M, Demain ED (2004) Lower bounds for dynamic connectivity. In: Proceedings of the 36th ACM symposium on theory of computing (STOC), pp 546\u2013553","DOI":"10.1145\/1007352.1007435"},{"key":"153_CR6325","unstructured":"P\u00e4trascu M, Tarnita C (2007) On dynamic bit-probe complexity. Theor Comput Sci Spec Issue ICALP'05 380:127\u2013142; In: Italiano GF, Palamidessi C (eds) A preliminary version in proceedings of the 32nd international colloquium on automata, languages and programming (ICALP'05), pp 969\u2013981"},{"key":"153_CR6326","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"RE Tarjan","year":"1985","unstructured":"Tarjan RE, Vishkin U (1985) An efficient parallel biconnectivity algorithm. SIAM J Comput 14:862\u2013874","journal-title":"SIAM J Comput"},{"key":"153_CR6327","doi-asserted-by":"crossref","unstructured":"Thorup M (2000) Near-optimal fully-dynamic graph connectivity. In: Proceedings of the 32nd ACM symposium on theory of computing (STOC), 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-1-4939-2864-4_153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:44:46Z","timestamp":1792107886000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_153","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}