{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:43:47Z","timestamp":1792111427016,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":10,"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_152","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:51:54Z","timestamp":1553097114000},"page":"792-793","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fully Dynamic Connectivity"],"prefix":"10.1007","author":[{"given":"Valerie","family":"King","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"5","key":"152_CR6301","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-a technique for speeding up dynamic graph algorithms. J ACM 44(5):669\u2013696.1","journal-title":"J ACM"},{"key":"152_CR6302","doi-asserted-by":"crossref","unstructured":"Henzinger MR, King V (1999) Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J ACM 46(4):502\u2013536. (Presented at ACM STOC 1995)","DOI":"10.1145\/320211.320215"},{"key":"152_CR6303","doi-asserted-by":"crossref","unstructured":"Henzinger MR, Thorup M (1997) Sampling to provide or to bound: with applications to fully dynamic graph algorithms. Random Struct Algorithms 11(4):369\u2013379. (Presented at ICALP 1996)","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<369::AID-RSA5>3.0.CO;2-X"},{"key":"152_CR6304","doi-asserted-by":"crossref","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(4):723\u2013760. (Presented at ACM STOC 1998)","DOI":"10.1145\/502090.502095"},{"key":"152_CR6305","doi-asserted-by":"crossref","unstructured":"Iyer R, Karger D, Rahul H, Thorup M (2001) An experimental study of poly-logarithmic fully-dynamic connectivity algorithms. J Exp Algorithmics 6(4). (Presented at ALENEX 2000)","DOI":"10.1145\/945394.945398"},{"key":"152_CR6306","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu M, Demaine E (2006) Logarithmic lower bounds in the cell-probe model. SIAM J Comput 35(4):932\u2013963. (Presented at ACM STOC 2004)","DOI":"10.1137\/S0097539705447256"},{"key":"152_CR6307","first-page":"343","volume-title":"Proceedings of the 32nd ACM symposium on theory of computing","author":"M Thorup","year":"2000","unstructured":"Thorup M (2000) Near-optimal fully-dynamic graph connectivity. In: Proceedings of the 32nd ACM symposium on theory of computing, Portland. ACM STOC, pp\u00a0343\u2013350"},{"key":"#cr-split#-152_CR6308.1","doi-asserted-by":"crossref","unstructured":"Thorup M (2000) Dynamic Graph Algorithms with Applications. In: Halld\u00f3rsson MM","DOI":"10.1007\/3-540-44985-X_1"},{"key":"#cr-split#-152_CR6308.2","unstructured":"(ed) 7th Scandinavian workshop on algorithm theory (SWAT), Norway, 5-7 July 2000, pp\u00a01-9"},{"key":"152_CR6309","doi-asserted-by":"crossref","unstructured":"Zaroliagis CD (2002) Implementations and experimental studies of dynamic graph algorithms. In: Experimental algorithmics, Dagstuhl seminar, Sept 2000. Lecture notes in computer science, vol\u00a02547. Springer. Journal article: J Exp Algorithmics 229\u2013278 (2000)","DOI":"10.1007\/3-540-36383-1_11"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:44:44Z","timestamp":1792107884000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_152","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"}}]}}