{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:34:14Z","timestamp":1794357254768,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":9,"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_152","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:35:59Z","timestamp":1214490959000},"page":"331-332","source":"Crossref","is-referenced-by-count":2,"title":["Fully Dynamic Connectivity"],"prefix":"10.1007","author":[{"given":"Valerie","family":"King","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"5","key":"152_CR1_152","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\u2013a\u00a0technique for speeding up dynamic graph algorithms. J.\u00a0ACM 44(5), 669\u2013696.1 (1997)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"152_CR2_152","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. ACM 46(4), 502\u2013536 (1999) (presented at ACM STOC 1995)","journal-title":"J. ACM"},{"issue":"4","key":"152_CR3_152","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<369::AID-RSA5>3.0.CO;2-X","volume":"11","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Thorup, M.: Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Struct. Algorithms 11(4), 369\u2013379 (1997) (presented at ICALP 1996)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"152_CR4_152","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.: Poly-logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree,  2-Edge, and Biconnectivity. J. ACM 48(4), 723\u2013760 (2001) (presented at ACM STOC 1998)","journal-title":"J. ACM"},{"key":"152_CR5_152","doi-asserted-by":"crossref","unstructured":"Iyer, R., Karger, D., Rahul, H., Thorup, M.: An experimental study of poly-logarithmic fully-dynamic connectivity algorithms. J.\u00a0Exp. Algorithmics 6(4) (2001) (presented at ALENEX 2000)","DOI":"10.1145\/945394.945398"},{"issue":"4","key":"152_CR6_152","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M. P\u0103tra\u015fcu","year":"2006","unstructured":"P\u0103tra\u015fcu, M., Demaine, E.: Logarithmic Lower Bounds in the Cell-Probe Model. SIAM J.\u00a0Comput. 35(4), 932\u2013963 (2006) (presented at ACM STOC 2004)","journal-title":"SIAM J. Comput."},{"key":"152_CR7_152","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of the 32th ACM Symposium on Theory of Computing pp.\u00a0343\u2013350. ACM STOC (2000)","DOI":"10.1145\/335305.335345"},{"key":"152_CR8_152","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Dynamic Graph Algorithms with Applications. In: Halld\u00f3rsson, M.M. (ed) 7th Scandinavian Workshop on Algorithm Theory (SWAT), Norway, 5\u20137 July 2000, pp.\u00a01\u20139","DOI":"10.1007\/3-540-44985-X_1"},{"key":"152_CR9_152","doi-asserted-by":"crossref","unstructured":"Zaroliagis, C.D.: Implementations and experimental studies of dynamic graph algorithms. In: Experimental Algorithmics, Dagstuhl seminar, September 2000, Lecture Notes in Computer Science, vol. 2547. Springer (2002), Journal Article: J.\u00a0Exp. 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-0-387-30162-4_152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T22:15:55Z","timestamp":1662156955000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_152"}},"subtitle":["2001; Holm, de Lichtenberg, Thorup"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_152","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]]}}}