{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:22:21Z","timestamp":1777965741865,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":20,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384270","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"336-349","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficient construction of directed hopsets and parallel approximate shortest paths"],"prefix":"10.1145","author":[{"given":"Nairen","family":"Cao","sequence":"first","affiliation":[{"name":"Georgetown University, USA"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[{"name":"Georgetown University, USA"}]},{"given":"Katina","family":"Russell","sequence":"additional","affiliation":[{"name":"Georgetown University, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384321"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935765"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1425"},{"key":"e_1_3_2_1_4_1","volume-title":"Eficient construction of directed hopsets and parallel approximate shortest paths. CoRR, abs\/","author":"Cao Nairen","year":"1912","unstructured":"Nairen Cao , Jeremy T. Fineman , and Katina Russell . Eficient construction of directed hopsets and parallel approximate shortest paths. CoRR, abs\/ 1912 .05506, 2019. Nairen Cao, Jeremy T. Fineman, and Katina Russell. Eficient construction of directed hopsets and parallel approximate shortest paths. CoRR, abs\/ 1912.05506, 2019."},{"key":"e_1_3_2_1_5_1","volume-title":"Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM, 47 ( 1 )","author":"Cohen Edith","year":"2000","unstructured":"Edith Cohen . Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM, 47 ( 1 ) : 132-166, January 2000 . Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM, 47 ( 1 ): 132-166, January 2000."},{"key":"e_1_3_2_1_6_1","first-page":"770","volume":"17","author":"Cole Richard","year":"1988","unstructured":"Richard Cole . Parallel merge sort. SIAM J. Comput. , 17 ( 4 ): 770 - 785 , August 1988 . Richard Cole. Parallel merge sort. SIAM J. Comput., 17 ( 4 ): 770-785, August 1988.","journal-title":"J. Comput."},{"key":"e_1_3_2_1_7_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2001","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Cliford Stein . Introduction to Algorithms . MIT Press , Cambridge, MA, USA , 2 nd edition, 2001 . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliford Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, USA, 2nd edition, 2001.","edition":"2"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/50087.50096"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.22"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323177"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188926"},{"key":"e_1_3_2_1_12_1","volume-title":"Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34 ( 3 )","author":"Michael","year":"1987","unstructured":"Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34 ( 3 ) : 596-615, July 1987 . Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34 ( 3 ): 596-615, July 1987."},{"key":"e_1_3_2_1_13_1","volume-title":"February","author":"Huang Shang-En","year":"2018","unstructured":"Shang-En Huang and Seth Pettie . Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts. ArXiv e-prints , February 2018 . Shang-En Huang and Seth Pettie. Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts. ArXiv e-prints, February 2018."},{"key":"e_1_3_2_1_14_1","first-page":"1664","volume-title":"60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","author":"Jambulapati Arun","year":"2019","unstructured":"Arun Jambulapati , Yang P. Liu , and Aaron Sidford . Parallel reachability in almost linear work and square root depth. In David Zuckerman, editor , 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 , Baltimore, Maryland, USA , November 9-12, 2019 , pages 1664 - 1686 . IEEE Computer Society, 2019. Arun Jambulapati, Yang P. Liu, and Aaron Sidford. Parallel reachability in almost linear work and square root depth. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1664-1686. IEEE Computer Society, 2019."},{"key":"e_1_3_2_1_15_1","volume-title":"A randomized parallel algorithm for single-source shortest paths. J. Algorithms, 25 ( 2 )","author":"Klein Philip N","year":"1997","unstructured":"Philip N Klein and Sairam Subramanian . A randomized parallel algorithm for single-source shortest paths. J. Algorithms, 25 ( 2 ) : 205-220, November 1997 . Philip N Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. J. Algorithms, 25 ( 2 ): 205-220, November 1997."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384268"},{"key":"e_1_3_2_1_17_1","first-page":"114","volume":"49","author":"Meyer U.","year":"2003","unstructured":"U. Meyer and P. Sanders . \u2206-stepping: A parallelizable shortest path algorithm. J. Algorithms , 49 ( 1 ): 114 - 152 , October 2003 . U. Meyer and P. Sanders. \u2206-stepping: A parallelizable shortest path algorithm. J. Algorithms, 49 ( 1 ): 114-152, October 2003.","journal-title":"\u2206-stepping: A parallelizable shortest path algorithm. J. Algorithms"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_1_19_1","volume-title":"Time-work tradeofs for parallel algorithms. J. ACM, 44 ( 5 )","author":"Spencer Thomas H.","year":"1997","unstructured":"Thomas H. Spencer . Time-work tradeofs for parallel algorithms. J. ACM, 44 ( 5 ) : 742-778, September 1997 . Thomas H. Spencer. Time-work tradeofs for parallel algorithms. J. ACM, 44 ( 5 ): 742-778, September 1997."},{"key":"e_1_3_2_1_20_1","first-page":"100","volume":"20","author":"Ullman Jefrey D.","year":"1991","unstructured":"Jefrey D. Ullman and Mihalis Yannakakis . High probability parallel transitiveclosure algorithms. SIAM J. Comput. , 20 ( 1 ): 100 - 125 , February 1991 . Jefrey D. Ullman and Mihalis Yannakakis. High probability parallel transitiveclosure algorithms. SIAM J. Comput., 20 ( 1 ): 100-125, February 1991.","journal-title":"J. Comput."}],"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.3384270","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384270","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.3384270"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":20,"alternative-id":["10.1145\/3357713.3384270","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384270","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"}}]}}