{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:39Z","timestamp":1781078199260,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1617727, CCF-1314633"],"award-info":[{"award-number":["CCF-1617727, CCF-1314633"]}],"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":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188926","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"457-470","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Nearly work-efficient parallel algorithm for digraph reachability"],"prefix":"10.1145","author":[{"given":"Jeremy T.","family":"Fineman","sequence":"first","affiliation":[{"name":"Georgetown University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Guy E. Blelloch Yan Gu Julian Shun and Yihan Sun. 2016.  Guy E. Blelloch Yan Gu Julian Shun and Yihan Sun. 2016."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935766"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_3_2_2_4_1","unstructured":"Richard Cole. 1988.  Richard Cole. 1988."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Parallel Merge Sort. SIAM J. Comput. 17 4 (Aug. 1988) 770\u2013785.  Parallel Merge Sort. SIAM J. Comput. 17 4 (Aug. 1988) 770\u2013785.","DOI":"10.1137\/0217049"},{"key":"e_1_3_2_2_6_1","unstructured":"Don Coppersmith Lisa Fleischer Bruce Hendrickson and Ali Pinar. 2005.  Don Coppersmith Lisa Fleischer Bruce Hendrickson and Ali Pinar. 2005."},{"key":"e_1_3_2_2_7_1","unstructured":"A divide-and-conquer algorithm for identifying strongly connected components. Technical Report RC23744. IBM Research.  A divide-and-conquer algorithm for identifying strongly connected components. Technical Report RC23744. IBM Research."},{"key":"e_1_3_2_2_8_1","unstructured":"Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2001.  Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2001."},{"key":"e_1_3_2_2_9_1","volume-title":"Introduction to Algorithms","edition":"2"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804339"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/72935.72953"},{"key":"e_1_3_2_2_12_1","unstructured":"Leslie M. Goldschlager. 1978.  Leslie M. Goldschlager. 1978."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804336"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644216"},{"key":"e_1_3_2_2_15_1","unstructured":"Shang-En Huang and Seth Pettie. 2018.  Shang-En Huang and Seth Pettie. 2018."},{"key":"e_1_3_2_2_16_1","volume-title":"ArXiv e-prints (Feb","author":"Sparse Spanners Lower Bounds","year":"2018"},{"key":"e_1_3_2_2_17_1","unstructured":"Joseph J\u00e1J\u00e1. 1992.  Joseph J\u00e1J\u00e1. 1992."},{"key":"e_1_3_2_2_18_1","unstructured":"An Introduction to Parallel Algorithms. Addison-Wesley.   An Introduction to Parallel Algorithms. Addison-Wesley."},{"key":"e_1_3_2_2_19_1","unstructured":"M.-Y. Kao and P. N. Klein. 1990.  M.-Y. Kao and P. N. Klein. 1990."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100237"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/195613.195632"},{"key":"e_1_3_2_2_22_1","volume-title":"Karp and Vijaya Ramachandran","author":"Richard","year":"1988"},{"key":"e_1_3_2_2_23_1","volume-title":"Technical Report UCB\/CSD-88-408. EECS Department","author":"Parallel A Survey","year":"1988"},{"key":"e_1_3_2_2_24_1","unstructured":"Philip N. Klein. 1993.  Philip N. Klein. 1993."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1017"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0888"},{"key":"e_1_3_2_2_27_1","unstructured":"Fran\u00e7ois Le Gall. 2014.  Fran\u00e7ois Le Gall. 2014."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322108.322119"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Warren Schudy. 2008.  Warren Schudy. 2008.","DOI":"10.12968\/sece.2008.12.1394"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378560"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265923"},{"key":"e_1_3_2_2_33_1","unstructured":"Mikkel Thorup. 1993.  Mikkel Thorup. 1993."},{"key":"e_1_3_2_2_34_1","volume-title":"Graph-Theoretic Concepts in Computer Science, Ernst W","author":"On"},{"key":"e_1_3_2_2_35_1","volume-title":"Ullman and Mihalis Yannakakis","author":"Jeffrey","year":"1991"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188926","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:10Z","timestamp":1750212430000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":35,"alternative-id":["10.1145\/3188745.3188926","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188926","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}