{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:03Z","timestamp":1781078283494,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1528078,CCF-1514339, BSF:2012338"],"award-info":[{"award-number":["CCF-1528078,CCF-1514339, BSF:2012338"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384236","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:11Z","timestamp":1624916891000},"page":"153-166","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["New algorithms and hardness for incremental single-source shortest paths in directed graphs"],"prefix":"10.1145","author":[{"given":"Maximilian","family":"Probst Gutenberg","sequence":"first","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Virginia","family":"Vassilevska Williams","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicole","family":"Wein","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.16"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061771"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_4_1","volume-title":"Proc. of CCC.","author":"Alman Josh","year":"2019","unstructured":"Josh Alman . 2019 . Limits on the Universal Method for Matrix Multiplication . In Proc. of CCC. to appear. Josh Alman. 2019. Limits on the Universal Method for Matrix Multiplication. In Proc. of CCC. to appear."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00061"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195179"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Raphael Yuster and Uri Zwick. 1997. Finding and Counting Given Length Cycles. Algorithmica 17 3 ( 1997 ) 209-223.  Noga Alon Raphael Yuster and Uri Zwick. 1997. Finding and Counting Given Length Cycles. Algorithmica 17 3 ( 1997 ) 209-223.","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_76"},{"key":"e_1_3_2_1_10_1","volume-title":"Constructing Light Spanners Deterministically in Near-Linear Time. In 27th Annual European Symposium on Algorithms (ESA 2019 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Alstrup Stephen","year":"2019","unstructured":"Stephen Alstrup , S\u00f8ren Dahlgaard , Arnold Filtser , Morten St\u00f6ckel , and Christian Wulf-Nilsen . 2019 . Constructing Light Spanners Deterministically in Near-Linear Time. In 27th Annual European Symposium on Algorithms (ESA 2019 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Stephen Alstrup, S\u00f8ren Dahlgaard, Arnold Filtser, Morten St\u00f6ckel, and Christian Wulf-Nilsen. 2019. Constructing Light Spanners Deterministically in Near-Linear Time. In 27th Annual European Symposium on Algorithms (ESA 2019 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of ICALP.","author":"Ancona Bertie","year":"2019","unstructured":"Bertie Ancona , Monika Henzinger , Liam Roditty , Virginia Vassilevska Williams , and Nicole Wein . 2019 . Algorithms and Hardness for Diameter in Dynamic Graphs . In Proceedings of ICALP. to appear. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. 2019. Algorithms and Hardness for Diameter in Dynamic Graphs. In Proceedings of ICALP. to appear."},{"key":"e_1_3_2_1_12_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP 2019 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Ancona Bertie","year":"2019","unstructured":"Bertie Ancona , Monika Henzinger , Liam Roditty , Virginia Vassilevska Williams , and Nicole Wein . 2019 . Algorithms and Hardness for Diameter in Dynamic Graphs. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. 2019. Algorithms and Hardness for Diameter in Dynamic Graphs. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_3_2_1_14_1","article-title":"A new approach to incremental cycle detection and related problems","volume":"12","author":"Bender Michael A","year":"2016","unstructured":"Michael A Bender , Jeremy T Fineman , Seth Gilbert , and Robert E Tarjan . 2016 . A new approach to incremental cycle detection and related problems . ACM Transactions on Algorithms (TALG) 12 , 2 ( 2016 ), 14. Michael A Bender, Jeremy T Fineman, Seth Gilbert, and Robert E Tarjan. 2016. A new approach to incremental cycle detection and related problems. ACM Transactions on Algorithms (TALG) 12, 2 ( 2016 ), 14.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.16"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938670"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175268"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897521"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039715"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175331"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316335"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.153"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884496"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.77"},{"key":"e_1_3_2_1_25_1","volume-title":"Eccentricity Spanner, and Approximating Extremal Graph Distances: Static, Dynamic, and Fault Tolerant. CoRR abs\/","author":"Choudhary Keerti","year":"1812","unstructured":"Keerti Choudhary and Omer Gold . 2018. Diameter Spanner , Eccentricity Spanner, and Approximating Extremal Graph Distances: Static, Dynamic, and Fault Tolerant. CoRR abs\/ 1812 .01602 ( 2018 ). arXiv: 1812.01602 http:\/\/arxiv.org\/abs\/ 1812.01602 Keerti Choudhary and Omer Gold. 2018. Diameter Spanner, Eccentricity Spanner, and Approximating Extremal Graph Distances: Static, Dynamic, and Fault Tolerant. CoRR abs\/ 1812.01602 ( 2018 ). arXiv: 1812.01602 http:\/\/arxiv.org\/abs\/ 1812.01602"},{"key":"e_1_3_2_1_26_1","volume-title":"A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. arXiv preprint arXiv","author":"Chuzhoy Julia","year":"1910","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. arXiv preprint arXiv : 1910 . 08025 ( 2019 ). 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. arXiv preprint arXiv: 1910. 08025 ( 2019 )."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316320"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"D. Coppersmith. 1997. Rectangular matrix multiplication revisited. Journal of Complexity 13 ( 1997 ) 42-49.  D. Coppersmith. 1997. Rectangular matrix multiplication revisited. Journal of Complexity 13 ( 1997 ) 42-49.","DOI":"10.1006\/jcom.1997.0438"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316329"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0308210511001648"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.22"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.155"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.154"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.24"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591869"},{"key":"e_1_3_2_1_41_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Henzinger Monika","unstructured":"Monika Henzinger , Sebastian Krinninger , and Danupon Nanongkai . 2015. Improved algorithms for decremental single-source reachability on directed graphs . In International Colloquium on Automata, Languages, and Programming . Springer , 725-736. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2015. Improved algorithms for decremental single-source reachability on directed graphs. In International Colloquium on Automata, Languages, and Programming. Springer, 725-736."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/140957299"},{"key":"e_1_3_2_1_43_1","article-title":"Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks","volume":"13","author":"Henzinger Monika","year":"2017","unstructured":"Monika Henzinger , Sebastian Krinninger , and Danupon Nanongkai . 2017 . Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks . ACM Transactions on Algorithms (TALG) 13 , 4 ( 2017 ), 1-24. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2017. Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks. ACM Transactions on Algorithms (TALG) 13, 4 ( 2017 ), 1-24.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796250"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.67"},{"key":"e_1_3_2_1_48_1","first-page":"1236","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"Lincoln Andrea","year":"2018","unstructured":"Andrea Lincoln , Virginia Vassilevska Williams , and R. Ryan Williams . 2018. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs . In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 , New Orleans, LA, USA , January 7-10, 2018 . 1236 - 1252 . Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. 2018. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018. 1236-1252."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806708"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Prabhakar Raghavan and Clark D Tompson. 1987. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7 4 ( 1987 ) 365-374.  Prabhakar Raghavan and Clark D Tompson. 1987. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7 4 ( 1987 ) 365-374.","DOI":"10.1007\/BF02579324"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_52"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210032"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_1_55_1","volume-title":"Proceedings of the International Congress of Mathematicians. 3431-3475","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams . 2018 . On some fine-grained questions in algorithms and complexity . In Proceedings of the International Congress of Mathematicians. 3431-3475 . Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians. 3431-3475."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_1_57_1","first-page":"254","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004","author":"Yuster Raphael","year":"2004","unstructured":"Raphael Yuster and Uri Zwick . 2004 . Detecting short directed cycles using rectangular matrix multiplication and dynamic programming . In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004 , New Orleans, Louisiana, USA , January 11-14, 2004. 254 - 260 . Raphael Yuster and Uri Zwick. 2004. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004. 254-260."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384236","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":58,"alternative-id":["10.1145\/3357713.3384236","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384236","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}