{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:26Z","timestamp":1740109406945,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,9,20]],"date-time":"2016-09-20T00:00:00Z","timestamp":1474329600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2014\/13\/B\/ST6\/01811"],"award-info":[{"award-number":["UMO-2014\/13\/B\/ST6\/01811"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Google (US)","award":["Focused Award on \"Algorithms for Large-scale Data Analysis\""],"award-info":[{"award-number":["Focused Award on \"Algorithms for Large-scale Data Analysis\""]}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["FET project MULTIPLEX no. 317532"],"award-info":[{"award-number":["FET project MULTIPLEX no. 317532"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00224-016-9709-x","type":"journal-article","created":{"date-parts":[[2016,9,20]],"date-time":"2016-09-20T02:00:06Z","timestamp":1474336806000},"page":"1037-1053","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Decremental Connectivity in Planar Graphs"],"prefix":"10.1007","volume":"61","author":[{"given":"Jakub","family":"\u0141\u0105cki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,20]]},"reference":[{"issue":"4","key":"9709_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0020-0190(97)00170-1","volume":"64","author":"S Alstrup","year":"1997","unstructured":"Alstrup, S., Secher, J.P., Spork, M.: Optimal on-line decremental connectivity in trees. Inf. Process. Lett. 64(4), 161\u2013164 (1997)","journal-title":"Inf. Process. Lett."},{"key":"9709_CR2","volume-title":"Improved sparsification. Information and Computer Science","author":"D Eppstein","year":"1993","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F.: Improved sparsification. Information and Computer Science. University of California, Irvine (1993)"},{"key":"9709_CR3","doi-asserted-by":"crossref","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 - a technique for speeding up dynamic graph algorithms. J. ACM 44, 669\u2013696 (1997)","journal-title":"J. ACM"},{"issue":"1","key":"9709_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1996.0002","volume":"52","author":"D Eppstein","year":"1996","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator based sparsification: I. Planarity testing and minimum spanning trees. J. Comput. Syst. Sci. 52(1), 3\u201327 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9709_CR5","doi-asserted-by":"crossref","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 minimum spanning forest in a dynamic plane graph. J. Algorithms 13(1), 33\u201354 (1992)","journal-title":"J. Algorithms"},{"issue":"4","key":"9709_CR6","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"GN Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781\u2013798 (1985)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9709_CR7","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9709_CR8","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01955676","volume":"16","author":"D Giammarresi","year":"1996","unstructured":"Giammarresi, D., Italiano, G.F.: Decremental 2- and 3-connectivity on planar graphs. Algorithmica 16(3), 263\u2013287 (1996)","journal-title":"Algorithmica"},{"issue":"1","key":"9709_CR9","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(97)00291-0","volume":"203","author":"J Gustedt","year":"1998","unstructured":"Gustedt, J.: Efficient union-find for planar graphs and other sparse graph classes. Theor. Comput. Sci. 203(1), 123\u2013141 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9709_CR10","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"MR Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"issue":"3","key":"9709_CR11","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/PL00009228","volume":"22","author":"MR 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":"9709_CR12","doi-asserted-by":"crossref","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)","journal-title":"J. ACM"},{"key":"9709_CR13","doi-asserted-by":"crossref","unstructured":"Kapron, B.M., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913, pages 1131\u20131142. SIAM (2013)","DOI":"10.1137\/1.9781611973105.81"},{"key":"9709_CR14","unstructured":"Kejlberg-Rasmussen, C., Kopelowitz, T., Pettie, S., Thorup, M.: Deterministic worst case dynamic connectivity: Simpler and faster. CoRR (2015). arXiv:\n                        1507.05944"},{"key":"9709_CR15","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Mozes, S., Sommer, C.: Structured recursive separator decompositions for planar graphs in linear time. In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1-4, 2013, pages 505\u2013514. ACM (2013)","DOI":"10.1145\/2488608.2488672"},{"issue":"4","key":"9709_CR16","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M Pa\u030ctra\u015fcu","year":"2006","unstructured":"Pa\u030ctra\u015fcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932\u2013963 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9709_CR17","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1006\/jcss.1996.0008","volume":"52","author":"JA La Poutr\u00e9","year":"1996","unstructured":"La Poutr\u00e9, J.A.: Lower bounds for the union-find and the sp;it-find problem on pointer machines. J. Comput. Syst. Sci. 52(1), 87\u201399 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9709_CR18","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215\u2013225 (1975)","journal-title":"J. ACM"},{"issue":"2","key":"9709_CR19","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"RE Tarjan","year":"1979","unstructured":"Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18(2), 110\u2013127 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9709_CR20","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1006\/jagm.1999.1033","volume":"33","author":"M Thorup","year":"1999","unstructured":"Thorup, M.: Decremental dynamic connectivity. J. Algorithms 33(2), 229\u2013243 (1999)","journal-title":"J. Algorithms"},{"key":"9709_CR21","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 343\u2013350, ACM, p 2000","DOI":"10.1145\/335305.335345"},{"key":"9709_CR22","unstructured":"van Walderveen, F., Zeh, N., Arge, L.: Multiway simple cycle separators I\/O-efficient algorithms for planar graphs. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 901\u2013918. SIAM, p 2013"},{"key":"9709_CR23","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Faster deterministic fully-dynamic graph connectivity. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1757\u20131769. SIAM, p 2013","DOI":"10.1137\/1.9781611973105.126"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9709-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9709-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9709-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,10,12]],"date-time":"2017-10-12T03:05:06Z","timestamp":1507777506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9709-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,20]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["9709"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9709-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,9,20]]}}}