{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T08:06:11Z","timestamp":1777622771472,"version":"3.51.4"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,1,23]],"date-time":"2022-01-23T00:00:00Z","timestamp":1642896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1314633, CCF-1617727, and CCF-1718700"],"award-info":[{"award-number":["CCF-1314633, CCF-1617727, and CCF-1718700"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            This article presents I\/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V, E<\/jats:italic>\n            ). Both algorithms are randomized and have I\/O-costs\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>sort<\/jats:italic>\n            (\n            <jats:italic>E<\/jats:italic>\n            ) \u00b7 poly(log V)), with high probability, where\n            <jats:italic>sort<\/jats:italic>\n            (\n            <jats:italic>E<\/jats:italic>\n            ) = O(\n            <jats:italic>E<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            log\n            <jats:sub>\n              <jats:italic>M<\/jats:italic>\n              \/\n              <jats:italic>B<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>E\/B<\/jats:italic>\n            )) is the I\/O cost of sorting an |\n            <jats:italic>E<\/jats:italic>\n            |-element array on a machine with size-\n            <jats:italic>B<\/jats:italic>\n            blocks and size-\n            <jats:italic>M<\/jats:italic>\n            cache\/internal memory. These are the first algorithms for these problems that do not incur at least one I\/O per vertex, and as such these are the first I\/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I\/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs.\n          <\/jats:p>","DOI":"10.1145\/3418356","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T05:51:05Z","timestamp":1643003465000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["I\/O-Efficient Algorithms for Topological Sort and Related Problems"],"prefix":"10.1145","volume":"18","author":[{"given":"Nairen","family":"Cao","sequence":"first","affiliation":[{"name":"Georgetown University, NW, Washington, DC, USA"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[{"name":"Georgetown University, NW, Washington, DC, USA"}]},{"given":"Katina","family":"Russell","sequence":"additional","affiliation":[{"name":"Georgetown University, NW, Washington, DC, USA"}]},{"given":"Eugene","family":"Yang","sequence":"additional","affiliation":[{"name":"Georgetown University, NW, Washington, DC, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,1,23]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/647908.740141"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/2790248.2790262"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/645930.672850"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.001"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/978-3-540-27836-8_15","volume-title":"Prooceedings of the 31st International Colloquium on Automata, Languages and Programming","author":"Arge Lars","year":"2004","unstructured":"Lars Arge, Ulrich Meyer, and Laura Toma. 2004. External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs. In Prooceedings of the 31st International Colloquium on Automata, Languages and Programming. 146\u2013157."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_116"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777427"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/338219.338650"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313681"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070536"},{"key":"e_1_3_2_13_2","article-title":"A labeling approach to incremental cycle detection","volume":"1310","author":"Cohen Edith","year":"2013","unstructured":"Edith Cohen, Amos Fiat, Haim Kaplan, and Liam Roditty. 2013. A labeling approach to incremental cycle detection. CoRR abs\/1310.8381. arXiv:1310.8381. http:\/\/arxiv.org\/abs\/1310.8381.","journal-title":"CoRR"},{"key":"e_1_3_2_14_2","volume-title":"A Divide-and-Conquer Algorithm for Identifying Strongly Connected Components","author":"Coppersmith Don","year":"2005","unstructured":"Don Coppersmith, Lisa Fleischer, Bruce Hendrickson, and Ali Pinar. 2005. A Divide-and-Conquer Algorithm for Identifying Strongly Connected Components. Technical Report RC23744. IBM Research."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/500824"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188926"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213899"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/829517.830723"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446925"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740673"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_49"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_49"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/314500.314891"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530929"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000014"},{"key":"e_1_3_2_28_2","unstructured":"Norbert Zeh. [n. d.]. I\/O-Efficient Graph Algorithms. Retrieved April 6 2018 from http:\/\/cs.au.dk\/large\/ioS05\/Znotes.pdf."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0372-z"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418356","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418356","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418356","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:27Z","timestamp":1750197747000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418356"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,23]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3418356"],"URL":"https:\/\/doi.org\/10.1145\/3418356","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,23]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}