{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:16:51Z","timestamp":1761808611133,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"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-1616584, CCF-2006464"],"award-info":[{"award-number":["CCF-1616584, CCF-2006464"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585196","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1159-1172","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths"],"prefix":"10.1145","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}]},{"given":"Ruimin","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Chicago, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Amir Abboud Karl Bringmann Seri Khoury and Or Zamir. 2022. Hardness of Approximation in P via Short Cycle Removal: Cycle Detection Distance Oracles and Beyond. arXiv preprint arXiv:2204.10465. Amir Abboud Karl Bringmann Seri Khoury and Or Zamir. 2022. Hardness of Approximation in P via Short Cycle Removal: Cycle Detection Distance Oracles and Beyond. arXiv preprint arXiv:2204.10465.","DOI":"10.1145\/3519935.3520066"},{"key":"e_1_3_2_1_2_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics. 28","author":"Abraham Ittai","year":"2014","unstructured":"Ittai Abraham , Shiri Chechik , and Kunal Talwar . 2014 . Fully dynamic all-pairs shortest paths: Breaking the O (n) barrier . In LIPIcs-Leibniz International Proceedings in Informatics. 28 . Ittai Abraham, Shiri Chechik, and Kunal Talwar. 2014. Fully dynamic all-pairs shortest paths: Breaking the O (n) barrier. In LIPIcs-Leibniz International Proceedings in Informatics. 28."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794271898"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89571"},{"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.","author":"Bergamaschi Thiago","year":"2020","unstructured":"Thiago Bergamaschi , Monika Henzinger , Maximilian Probst Gutenberg , Virginia Vassilevska Williams, and Nicole Wein. 2020 . New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners . arXiv preprint arXiv:2010.10134. Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. 2020. New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. arXiv preprint arXiv:2010.10134."},{"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":"Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. In LIPIcs-Leibniz International Proceedings in Informatics. 80","author":"Bernstein Aaron","year":"2017","unstructured":"Aaron Bernstein . 2017 . Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. In LIPIcs-Leibniz International Proceedings in Informatics. 80 . Aaron Bernstein. 2017. Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. In LIPIcs-Leibniz International Proceedings in Informatics. 80."},{"key":"e_1_3_2_1_10_1","volume-title":"Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun.","author":"Bernstein Aaron","year":"2020","unstructured":"Aaron Bernstein , Jan van den Brand , Maximilian Probst Gutenberg , Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. 2020 . Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432. Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. 2020. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897521"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00100"},{"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","doi-asserted-by":"crossref","unstructured":"Jan van den Brand Sebastian Forster and Yasamin Nazari. 2021. Fast Deterministic Fully Dynamic Distance Approximation. arXiv preprint arXiv:2111.03361. Jan van den Brand Sebastian Forster and Yasamin Nazari. 2021. Fast Deterministic Fully Dynamic Distance Approximation. arXiv preprint arXiv:2111.03361.","DOI":"10.1109\/FOCS54457.2022.00099"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00025"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.28"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451025"},{"key":"e_1_3_2_1_18_1","volume-title":"SODA","author":"Chuzhoy Julia","year":"2022","unstructured":"Julia Chuzhoy . 2022 . A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems . SODA 2023, to appear. Full version available at https:\/\/home.ttic.edu\/ cjulia\/papers\/APSP-expanders.pdf Julia Chuzhoy. 2022. A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems. SODA 2023, to appear. Full version available at https:\/\/home.ttic.edu\/ cjulia\/papers\/APSP-expanders.pdf"},{"key":"e_1_3_2_1_19_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 . 2019. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. CoRR, abs\/1910.08025 ( 2019 ), arxiv:1910.08025. arxiv:1910.08025 Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. 2019. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. CoRR, abs\/1910.08025 (2019), arxiv:1910.08025. arxiv:1910.08025"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316320"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.147"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"volume-title":"Dinitz","author":"Dinitz Yefim","key":"e_1_3_2_1_23_1","unstructured":"Yefim Dinitz . 2006. Dinitz \u2019 algorithm: The original version and Even\u2019s version. In Theoretical computer science. Springer , 218\u2013240. Yefim Dinitz. 2006. Dinitz\u2019 algorithm: The original version and Even\u2019s version. In Theoretical computer science. Springer, 218\u2013240."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316381"},{"key":"e_1_3_2_1_27_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 . 2020. Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications. CoRR, abs\/2004.10319 ( 2020 ), arxiv:2004.10319. arxiv:2004.10319 Sebastian Forster, Gramoz Goranci, and Monika Henzinger. 2020. Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications. CoRR, abs\/2004.10319 (2020), arxiv:2004.10319. arxiv:2004.10319"},{"key":"e_1_3_2_1_28_1","volume-title":"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","author":"Forster Sebastian","year":"2014","unstructured":"Sebastian Forster , Monika Henzinger , and Danupon Nanongkai . 2014 . 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. 146\u2013155. Sebastian Forster, Monika Henzinger, and Danupon Nanongkai. 2014. 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. 146\u2013155."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.154"},{"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","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492668"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327209"},{"key":"e_1_3_2_1_34_1","unstructured":"Adam Karczmarz and Jakub \u0141 acki. 2019. Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs. arXiv preprint arXiv:1907.02266. Adam Karczmarz and Jakub \u0141 acki. 2019. Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs. arXiv preprint arXiv:1907.02266."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538903"},{"key":"e_1_3_2_1_36_1","unstructured":"Jakub \u0141 acki and Yasamin Nazari. 2020. Near-Optimal Decremental Approximate Multi-Source Shortest Paths. arXiv preprint arXiv:2009.08416. Jakub \u0141 acki and Yasamin Nazari. 2020. Near-Optimal Decremental Approximate Multi-Source Shortest Paths. arXiv preprint arXiv:2009.08416."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/090776573"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_33"},{"volume-title":"Annual ACM Symposium on Theory of Computing.","author":"Thorup M.","key":"e_1_3_2_1_41_1","unstructured":"M. Thorup and U. Zwick . 2001. Approximate distance oracles . Annual ACM Symposium on Theory of Computing. M. Thorup and U. Zwick. 2001. Approximate distance oracles. Annual ACM Symposium on Theory of Computing."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585196","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585196","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:01Z","timestamp":1750178821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":42,"alternative-id":["10.1145\/3564246.3585196","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585196","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}