{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:34Z","timestamp":1781077774849,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2006464"],"award-info":[{"award-number":["CCF-2006464"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["CCF-1616584"],"award-info":[{"award-number":["CCF-1616584"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451025","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"626-639","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Decremental all-pairs shortest paths in deterministic near-linear time"],"prefix":"10.1145","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"28","author":"Abraham Ittai","year":"2014","unstructured":"Ittai Abraham, Shiri Chechik, and Kunal Talwar. Fully dynamic all-pairs shortest paths: Breaking the O (n) barrier. In LIPIcs-Leibniz International Proceedings in Informatics, volume 28. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794271898"},{"key":"e_1_3_2_1_4_1","first-page":"513","volume-title":"Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science","author":"Awerbuch Baruch","unstructured":"Baruch Awerbuch and David Peleg. Sparse partitions. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 503\u2013513. IEEE, 1990."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.08.004"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"e_1_3_2_1_7_1","volume-title":"Virginia Vassilevska Williams, and Nicole Wein. New techniques and fine-grained hardness for dynamic near-additive spanners. arXiv preprint arXiv:2010.10134","author":"Bergamaschi Thiago","year":"2020","unstructured":"Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New techniques and fine-grained hardness for dynamic near-additive spanners. arXiv preprint arXiv:2010.10134, 2020."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938670"},{"key":"e_1_3_2_1_9_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"80","author":"Bernstein Aaron","year":"2017","unstructured":"Aaron Bernstein. Deterministic partially dynamic single source shortest paths in weighted graphs. In LIPIcs-Leibniz International Proceedings in Informatics, volume 80. Schloss Dagstuhl-Leibniz-Center for Computer Science, 2017."},{"key":"e_1_3_2_1_10_1","volume-title":"Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432","author":"Bernstein Aaron","year":"2020","unstructured":"Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432, 2020."},{"key":"e_1_3_2_1_11_1","first-page":"397","volume-title":"Proceedings of the forty-eighth annual ACM symposium on Theory of Computing","author":"Bernstein Aaron","unstructured":"Aaron Bernstein and Shiri Chechik. Deterministic decremental single source shortest paths: beyond the O(mn) bound. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 389\u2013397. ACM, 2016."},{"key":"e_1_3_2_1_12_1","first-page":"469","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bernstein Aaron","unstructured":"Aaron Bernstein and Shiri Chechik. Deterministic partially dynamic single source shortest paths for sparse graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 453\u2013469. SIAM, 2017."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.104"},{"key":"e_1_3_2_1_14_1","first-page":"181","volume-title":"2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Chechik Shiri","unstructured":"Shiri Chechik. Near-optimal approximate decremental all pairs shortest paths. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 170\u2013181. IEEE, 2018."},{"key":"e_1_3_2_1_15_1","first-page":"475","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chechik Shiri","unstructured":"Shiri Chechik and Tianyi Zhang. Dynamic low-stretch spanning trees in subpolynomial time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 463\u2013475. SIAM, 2020."},{"key":"e_1_3_2_1_16_1","volume-title":"A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. CoRR, abs\/1910.08025","author":"Chuzhoy Julia","year":"2019","unstructured":"Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. CoRR, abs\/1910.08025, 2019."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316320"},{"key":"e_1_3_2_1_18_1","first-page":"2496","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chuzhoy Julia","unstructured":"Julia Chuzhoy and Thatchaphol Saranurak. Deterministic algorithms for decremental shortest paths via layered core decomposition. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2478\u20132496. SIAM, 2021."},{"key":"e_1_3_2_1_19_1","volume-title":"Springer","author":"Dinitz Yefim","year":"2006","unstructured":"Yefim Dinitz. Dinitz' algorithm: The original version and Even's version. In Theoretical computer science, pages 218\u2013240. Springer, 2006."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"e_1_3_2_1_21_1","volume-title":"An on-line edge-deletion problem. Journal of the ACM (JACM), 28(1):1\u20134","author":"Even Shimon","year":"1981","unstructured":"Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. Journal of the ACM (JACM), 28(1):1\u20134, 1981."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316381"},{"key":"e_1_3_2_1_24_1","volume-title":"Dynamic maintenance of low-stretch probabilistic tree embeddings with applications. CoRR, abs\/2004.10319","author":"Forster Sebastian","year":"2020","unstructured":"Sebastian Forster, Gramoz Goranci, and Monika Henzinger. Dynamic maintenance of low-stretch probabilistic tree embeddings with applications. CoRR, abs\/2004.10319, 2020."},{"key":"e_1_3_2_1_25_1","first-page":"155","volume-title":"55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014","author":"Forster Sebastian","year":"2014","unstructured":"Sebastian Forster, Monika Henzinger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 146\u2013155, 2014."},{"key":"e_1_3_2_1_26_1","first-page":"1072","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014","author":"Forster Sebastian","year":"2014","unstructured":"Sebastian Forster, Monika Henzinger, and Danupon Nanongkai. A subquadratic-time algorithm for decremental single-source shortest paths. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1053\u20131072, 2014."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796457"},{"key":"e_1_3_2_1_29_1","first-page":"2541","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Gutenberg Maximilian Probst","unstructured":"Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Deterministic algorithms for decremental approximate shortest paths: Faster and simpler. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2522\u20132541. SIAM, 2020."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/140957299"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_32_1","first-page":"672","volume-title":"Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on","author":"Henzinger Monika Rauch","unstructured":"Monika Rauch Henzinger and Valerie King. Fully dynamic biconnectivity and transitive closure. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, pages 664\u2013672. IEEE, 1995."},{"key":"e_1_3_2_1_33_1","volume-title":"Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs. arXiv preprint arXiv:1907.02266","author":"Karczmarz Adam","year":"2019","unstructured":"Adam Karczmarz and Jakub \\Lacki. Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs. arXiv preprint arXiv:1907.02266, 2019."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213979"},{"key":"e_1_3_2_1_35_1","volume-title":"Graph partitioning using single commodity flows. Journal of the ACM (JACM), 56(4):19","author":"Khandekar Rohit","year":"2009","unstructured":"Rohit Khandekar, Satish Rao, and Umesh Vazirani. Graph partitioning using single commodity flows. Journal of the ACM (JACM), 56(4):19, 2009."},{"key":"e_1_3_2_1_36_1","volume-title":"Near-optimal decremental approximate multi-source shortest paths. arXiv preprint arXiv:2009.08416","author":"Lacki Jakub","year":"2020","unstructured":"Jakub \\Lacki and Yasamin Nazari. Near-optimal decremental approximate multi-source shortest paths. arXiv preprint arXiv:2009.08416, 2020."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806708"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/090776573"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.162"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380798"},{"key":"e_1_3_2_1_43_1","volume-title":"Subcubic equivalences between path, matrix, and triangle problems. Journal of the ACM (JACM), 65(5):1\u201338","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams and R Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. Journal of the ACM (JACM), 65(5):1\u201338, 2018."},{"key":"e_1_3_2_1_44_1","first-page":"319","volume-title":"Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280)","author":"Zwick Uri","unstructured":"Uri Zwick. All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 310\u2013319. IEEE, 1998."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451025","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451025","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":44,"alternative-id":["10.1145\/3406325.3451025","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451025","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}