{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:02:45Z","timestamp":1750492965599,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030247652"},{"type":"electronic","value":"9783030247669"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_40","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"553-565","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimal Offline Dynamic 2,\u00a03-Edge\/Vertex Connectivity"],"prefix":"10.1007","author":[{"given":"Richard","family":"Peng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bryce","family":"Sandlund","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel D.","family":"Sleator","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Dahlgaard, S.: Popular conjectures as a barrier for dynamic planar graph algorithms. In: IEEE 57th Annual Symposium on Foundations of Computer Science, pp. 477\u2013486, Nov 2016","DOI":"10.1109\/FOCS.2016.58"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 434\u2013443 (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V., Yu, H.: Matching triangles and basing hardness on an extremely popular conjecture. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pp. 41\u201350 (2015)","DOI":"10.1145\/2746539.2746594"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Abraham, I., Durfee, D., Koutis, I., Krinninger, S., Peng, R.: On fully dynamic graph sparsifiers. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 335\u2013344, Oct 2016","DOI":"10.1109\/FOCS.2016.44"},{"key":"40_CR5","unstructured":"Assadi, S., Khanna, S., Li, Y., Tannen, V.: Dynamic sketching for graph optimization problems with applications to cut-preserving sketches. In: FSTTCS (2015)"},{"key":"40_CR6","unstructured":"Bringmann, K., Kunnemann, M., Nusser, A.: Frechet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability. CoRR abs\/1810.10982 (2018). https:\/\/arxiv.org\/abs\/1810.10982"},{"key":"40_CR7","unstructured":"Dahlgaard, S.: On the hardness of partially dynamic graph problems and connections to diameter. In: 43rd International Colloquium on Automata, Languages, and Programming (2016)"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Durfee, D., Gao, Y., Goranci, G., Peng, R.: Fully dynamic spectral vertex sparsifiers and applications. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing, STOC 2019. ACM (2019)","DOI":"10.1145\/3313276.3316379"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Durfee, D., Kyng, R., Peebles, J., Rao, A.B., Sachdeva, S.: Sampling random spanning trees faster than matrix multiplication. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 730\u2013742 (2017)","DOI":"10.1145\/3055399.3055499"},{"issue":"2","key":"40_CR10","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jagm.1994.1033","volume":"17","author":"D Eppstein","year":"1994","unstructured":"Eppstein, D.: Offline algorithms for dynamic minimum spanning tree problems. J. Algorithms 17(2), 237\u2013250 (1994)","journal-title":"J. Algorithms"},{"issue":"5","key":"40_CR11","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-a technique for speeding up dynamic graph algorithms. J. ACM 44(5), 669\u2013696 (1997)","journal-title":"J. ACM"},{"issue":"1","key":"40_CR12","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/S0097539794269072","volume":"28","author":"D Eppstein","year":"2006","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator-based sparsification II: edge and vertex connectivity. SIAM J. Comput. 28(1), 341\u2013381 (2006)","journal-title":"SIAM J. Comput."},{"key":"40_CR13","unstructured":"Fafianie, S., Hols, E.M.C., Kratsch, S., Quyen, V.A.: Preprocessing under uncertainty: matroid intersection. In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, vol. 58, pp. 35:1\u201335:14 (2016)"},{"key":"40_CR14","unstructured":"Fafianie, S., Kratsch, S., Quyen, V.A.: Preprocessing under uncertainty. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, vol. 47, pp. 33:1\u201333:13 (2016)"},{"key":"40_CR15","unstructured":"Goranci, G., Henzinger, M., Peng, P.: The power of vertex sparsifiers in dynamic graph algorithms. In: European Symposium on Algorithms (ESA), pp. 45:1\u201345:14 (2017)"},{"key":"40_CR16","unstructured":"Goranci, G., Henzinger, M., Peng, P.: Dynamic effective resistances and approximate schur complement on separable graphs. In: 26th Annual European Symposium on Algorithms, ESA 2018, vol. 112, pp. 40:1\u201340:15 (2018)"},{"key":"40_CR17","unstructured":"Goranci, G., Henzinger, M., Saranurak, T.: Fast incremental algorithms via local sparsifiers. CoRR (2018). https:\/\/drive.google.com\/file\/d\/1SJrbzuz_szMwsBfeBZfGUWkDEbZKAGD5\/view"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing, STOC 1998, pp. 79\u201389. ACM, New York (1998)","DOI":"10.1145\/276698.276715"},{"key":"40_CR19","unstructured":"Holm, J., Rotenberg, E., Thorup, M.: Dynamic bridge-finding in $$\\tilde{O}(\\log ^2 n)$$ amortized time. In: Symposium on Discrete Algorithms (SODA) (2018)"},{"key":"40_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/978-3-662-48350-3_62","volume-title":"Algorithms \u2013 ESA 2015","author":"J Holm","year":"2015","unstructured":"Holm, J., Rotenberg, E., Wulff-Nilsen, C.: Faster fully-dynamic minimum spanning forest. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 742\u2013753. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_62"},{"issue":"3","key":"40_CR21","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"40_CR22","doi-asserted-by":"crossref","unstructured":"Huang, S.E., Huang, D., Kopelowitz, T., Pettie, S.: Fully dynamic connectivity in $$O(\\log n(\\log \\log n)^2)$$ amortized expected time. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 510\u2013520 (2017)","DOI":"10.46298\/theoretics.23.6"},{"key":"40_CR23","doi-asserted-by":"crossref","unstructured":"Kapron, B., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: SODA (2013)","DOI":"10.1137\/1.9781611973105.81"},{"key":"40_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/978-3-319-21840-3_38","volume-title":"Algorithms and Data Structures","author":"A Karczmarz","year":"2015","unstructured":"Karczmarz, A., \u0141\u0105cki, J.: Fast and simple connectivity in graph timelines. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 458\u2013469. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_38"},{"issue":"1","key":"40_CR25","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"DR Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47(1), 46\u201376 (2000)","journal-title":"J. ACM"},{"key":"40_CR26","unstructured":"Kopeliovich, S.: Offline solution of connectivity and $$2$$-edge-connectivity problems for fully dynamic graphs. Master\u2019s thesis, Saint Petersburg State University (2012)"},{"key":"40_CR27","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstrom, M.: Representative sets and irrelevant vertices: New tools for kernelization. In: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS 2012, pp. 450\u2013459 (2012)","DOI":"10.1109\/FOCS.2012.46"},{"key":"40_CR28","unstructured":"Li, H., Patterson, S., Yi, Y., Zhang, Z.: Maximizing the number of spanning trees in a connected graph. CoRR abs\/1804.02785 (2018). https:\/\/arxiv.org\/abs\/1804.02785"},{"key":"40_CR29","doi-asserted-by":"publisher","first-page":"2377","DOI":"10.1137\/1.9781611975031.153","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Huan Li","year":"2018","unstructured":"Li, H., Zhang, Z.: Kirchhoff index as a measure of edge centrality in weighted networks: nearly linear time algorithms. In: Symposium on Discrete Algorithms (SODA), pp. 2377\u20132396 (2018)"},{"key":"40_CR30","doi-asserted-by":"crossref","unstructured":"\u0141\u0105cki, J., Sankowski, P.: Reachability in graph timelines. In: ITCS (2013)","DOI":"10.1145\/2422436.2422468"},{"key":"40_CR31","unstructured":"Molina, A., Sandlund, B.: Personal communication"},{"key":"40_CR32","doi-asserted-by":"crossref","unstructured":"Patracscu, M., Demaine, E.D.: Lower bounds for dynamic connectivity. In: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, STOC 2004, pp. 546\u2013553. ACM, New York (2004)","DOI":"10.1145\/1007352.1007435"},{"key":"40_CR33","unstructured":"Peng, R., Sandlund, B., Sleator, D.D.: Offline dynamic higher connectivity. CoRR abs\/1708.03812 (2017). http:\/\/arxiv.org\/abs\/1708.03812"},{"key":"40_CR34","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 omputing, STOC 2000, pp. 343\u2013350, ACM, New York (2000)","DOI":"10.1145\/335305.335345"},{"issue":"1","key":"40_CR35","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.jda.2008.04.003","volume":"7","author":"YH Tsin","year":"2009","unstructured":"Tsin, Y.H.: Yet another optimal algorithm for 3-edge-connectivity. J. Discrete Algorithms 7(1), 130\u2013146 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"40_CR36","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Fully-dynamic minimum spanning forest with improved worst-case update time. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1130\u20131143 (2017)","DOI":"10.1145\/3055399.3055415"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-24766-9_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:56:12Z","timestamp":1710266172000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}