{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:51:57Z","timestamp":1758271917463,"version":"3.37.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319731162"},{"type":"electronic","value":"9783319731179"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","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":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_3","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T16:45:34Z","timestamp":1513874734000},"page":"40-44","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The State of the Art in Dynamic Graph Algorithms"],"prefix":"10.1007","author":[{"given":"Monika","family":"Henzinger","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Dahlgaard, S.: Popular conjectures as a barrier for dynamic planar graph algorithms. In: FOCS (2016)","DOI":"10.1109\/FOCS.2016.58"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: FOCS (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 782\u2013793. Society for Industrial and Applied Mathematics (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Eppstein, D., Guibas, L.J., Henzinger, M.R.: Parametric and kinetic minimum spanning trees. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 596\u2013605. IEEE (1998)","DOI":"10.1109\/SFCS.1998.743510"},{"key":"3_CR5","unstructured":"Anand, A., Baswana, S., Gupta, M., Sen, S.: Maintaining approximate maximum weighted matching in fully dynamic graphs. In: D\u2019Souza, D., Kavitha, T., Radhakrishnan, J. (eds.) FSTTCS. LIPIcs, vol. 18, pp. 257\u2013266. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"issue":"1","key":"3_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1998.0988","volume":"31","author":"J Basch","year":"1999","unstructured":"Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. J. Algorithms 31(1), 1\u201328 (1999)","journal-title":"J. Algorithms"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in $$\\cal{O}(\\log n)$$ O ( log n ) update time. In: FOCS (2011). http:\/\/dx.doi.org\/10.1137\/130914140","DOI":"10.1137\/130914140"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Karger, D.: A nearly optimal oracle for avoiding failed vertices and edges. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 101\u2013110. ACM (2009)","DOI":"10.1145\/1536414.1536431"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-662-47672-7_14","volume-title":"Automata, Languages, and Programming","author":"A Bernstein","year":"2015","unstructured":"Bernstein, A., Stein, C.: Fully dynamic matching in bipartite graphs. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 167\u2013179. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47672-7_14"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Stein, C.: Faster fully dynamic matchings with small approximation ratios. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 692\u2013711. Society for Industrial and Applied Mathematics (2016)","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-319-59250-3_8","volume-title":"Integer Programming and Combinatorial Optimization","author":"S Bhattacharya","year":"2017","unstructured":"Bhattacharya, S., Chakrabarty, D., Henzinger, M.: Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In: Eisenbrand, F., Koenemann, J. (eds.) IPCO 2017. LNCS, vol. 10328, pp. 86\u201398. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-59250-3_8"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. In: SODA (2015)","DOI":"10.1137\/1.9781611973730.54"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D.: New deterministic approximation algorithms for fully dynamic matching. In: STOC 2016","DOI":"10.1145\/2897518.2897568"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D.: Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 470\u2013489. SIAM (2017)","DOI":"10.1137\/1.9781611974782.30"},{"issue":"3","key":"3_CR15","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1137\/S009753970343912X","volume":"36","author":"TM Chan","year":"2006","unstructured":"Chan, T.M.: Dynamic subgraph connectivity with geometric applications. SIAM J. Comput. 36(3), 681\u2013694 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_CR16","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1007\/s00453-011-9543-0","volume":"63","author":"S Chechik","year":"2012","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: F-sensitivity distance oracles and routing schemes. Algorithmica 63(4), 861\u2013882 (2012)","journal-title":"Algorithmica"},{"key":"3_CR17","unstructured":"Dahlgaard, S.: On the hardness of partially dynamic graph problems and connections to diameter. In: ICALP, pp. 48:1\u201348:14 (2016)"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Connectivity oracles for failure prone graphs. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 465\u2013474. ACM (2010)","DOI":"10.1145\/1806689.1806754"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator based sparsification for dynamic planar graph algorithms. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 208\u2013217. ACM (1993)","DOI":"10.1145\/167088.167159"},{"issue":"1","key":"3_CR20","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/s004530010032","volume":"28","author":"D Frigioni","year":"2000","unstructured":"Frigioni, D., Italiano, G.F.: Dynamically switching vertices in planar graphs. Algorithmica 28(1), 76\u2013103 (2000)","journal-title":"Algorithmica"},{"issue":"2","key":"3_CR21","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/jagm.1999.1048","volume":"34","author":"D Frigioni","year":"2000","unstructured":"Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithms 34(2), 251\u2013281 (2000)","journal-title":"J. Algorithms"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Gupta, M., Peng, R.: Fully dynamic $$(1+\\epsilon )$$ ( 1 + \u03f5 ) -approximate matchings. In: FOCS (2013)","DOI":"10.1109\/FOCS.2013.65"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: Decremental single-source shortest paths on undirected graphs in near-linear total update time. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 146\u2013155. IEEE (2014)","DOI":"10.1109\/FOCS.2014.24"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: STOC (2015)","DOI":"10.1145\/2746539.2746609"},{"key":"3_CR25","unstructured":"Henzinger, M., Lincoln, A., Neumann, S., Williams, V.V.: Conditional hardness for sensitivity problems. In: ITCS (2017)"},{"key":"3_CR26","unstructured":"Henzinger, M., Neumann, S.: Incremental and fully dynamic subgraph connectivity for emergency planning. In: ESA (2016)"},{"issue":"4","key":"3_CR27","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 (JACM) 46(4), 502\u2013516 (1999)","journal-title":"J. ACM (JACM)"},{"issue":"3","key":"3_CR28","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":"3_CR29","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 (JACM) 48(4), 723\u2013760 (2001)","journal-title":"J. ACM (JACM)"},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/3-540-57273-2_57","volume-title":"Algorithms\u2014ESA \u201993","author":"GF Italiano","year":"1993","unstructured":"Italiano, G.F., La Poutr\u00e9, J.A., Rauch, M.H.: Fully dynamic planarity testing in planar embedded graphs. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 212\u2013223. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-57273-2_57"},{"issue":"3","key":"3_CR31","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/PL00009223","volume":"22","author":"PN Klein","year":"1998","unstructured":"Klein, P.N., Subramanian, S.: A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 22(3), 235\u2013249 (1998)","journal-title":"Algorithmica"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3 sum conjecture. In: SODA, pp. 1272\u20131287 (2016)","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Weinstein, O., Yu, H.: Crossing the logarithmic barrier for dynamic boolean data structure lower bounds. arXiv preprint arXiv:1703.03575 (2017)","DOI":"10.1145\/3188745.3188790"},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: STOC (2013)","DOI":"10.1145\/2488608.2488703"},{"issue":"4","key":"3_CR35","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M Patrascu","year":"2006","unstructured":"Patrascu, 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."},{"key":"3_CR36","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Planning for fast connectivity updates. In: 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, FOCS 2007, pp. 263\u2013271. IEEE (2007)","DOI":"10.1109\/FOCS.2007.59"},{"key":"3_CR37","doi-asserted-by":"crossref","unstructured":"Peleg, D., Solomon, S.: Dynamic (1+ $$\\epsilon $$ \u03f5 )-approximate matchings: a density-sensitive approach. In: SODA (2016)","DOI":"10.1137\/1.9781611974331.ch51"},{"key":"3_CR38","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: SODA (2007)"},{"key":"3_CR39","doi-asserted-by":"crossref","unstructured":"Solomon, S.: Fully dynamic maximal matching in constant update time. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 325\u2013334. IEEE (2016)","DOI":"10.1109\/FOCS.2016.43"},{"key":"3_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/3-540-57273-2_72","volume-title":"Algorithms\u2014ESA \u201993","author":"S Subramanian","year":"1993","unstructured":"Subramanian, S.: A fully dynamic data structure for reachability in planar digraphs. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 372\u2013383. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-57273-2_72"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,24]],"date-time":"2020-10-24T17:45:57Z","timestamp":1603561557000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}