{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T01:12:01Z","timestamp":1774228321393,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,12,8]],"date-time":"2015-12-08T00:00:00Z","timestamp":1449532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-0621439, CCF-0540897, CCF-0634793, CNS-0627645, CNS-1408695, CCF-1439084, IIS-1247726, IIS-1251137, CCF-1217708, and CCF-1114809"],"award-info":[{"award-number":["CCF-0621439, CCF-0540897, CCF-0634793, CNS-0627645, CNS-1408695, CCF-1439084, IIS-1247726, IIS-1251137, CCF-1217708, and CCF-1114809"]}]},{"name":"MOEARC-2","award":["CCF-0832797 and MOE2014-T2-1-157"],"award-info":[{"award-number":["CCF-0832797 and MOE2014-T2-1-157"]}]},{"name":"U.S.-Israel Binational Science Foundation","award":["2006204"],"award-info":[{"award-number":["2006204"]}]},{"name":"NSF\/CRA- sponsored CIFellows program","award":["CCF-1218188, CCF-1314633"],"award-info":[{"award-number":["CCF-1218188, CCF-1314633"]}]},{"name":"Distinguished Visitor program in the Stanford University Computer Science Department"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"<jats:p>\n            We consider the problem of detecting a cycle in a directed graph that grows by arc insertions and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one suited to sparse graphs, the other to dense graphs. The former takes\n            <jats:italic>O<\/jats:italic>\n            (min {\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>1\/2<\/jats:sup>\n            ,\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            }\n            <jats:italic>m<\/jats:italic>\n            ) time to insert\n            <jats:italic>m<\/jats:italic>\n            arcs into an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph; the latter takes\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time. Our sparse algorithm is substantially simpler than a previous\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            )-time algorithm; it is also faster on graphs of sufficient density. The time bound of our dense algorithm beats the previously best time bound of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>5\/2<\/jats:sup>\n            ) for dense graphs. Our algorithms rely for their efficiency on vertex numberings weakly consistent with topological order: we allow ties. Bounds on the size of the numbers give bounds on running time.\n          <\/jats:p>","DOI":"10.1145\/2756553","type":"journal-article","created":{"date-parts":[[2015,12,10]],"date-time":"2015-12-10T14:22:10Z","timestamp":1449757330000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["A New Approach to Incremental Cycle Detection and Related Problems"],"prefix":"10.1145","volume":"12","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington, DC"}]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton University and Intertrust Technologies, Sunnyvale, CA"}]}],"member":"320","published-online":{"date-parts":[[2015,12,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ISAAC (Lecture Notes in Computer Science)","author":"Ajwani Deepak","unstructured":"Deepak Ajwani and Tobias Friedrich . 2007. Average-case analysis of online topological ordering . In ISAAC (Lecture Notes in Computer Science) , Takeshi Tokuyama (Ed.), Vol. 4835 . Springer , 464--475. Deepak Ajwani and Tobias Friedrich. 2007. Average-case analysis of online topological ordering. In ISAAC (Lecture Notes in Computer Science), Takeshi Tokuyama (Ed.), Vol. 4835. Springer, 464--475."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785293_8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383370"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. 32--42","author":"Alpern Bowen","unstructured":"Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , and F. Kenneth Zadeck . 1990. Incremental evaluation of computational circuits . In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. 32--42 . Bowen Alpern, Roger Hoover, Barry K. Rosen, Peter F. Sweeney, and F. Kenneth Zadeck. 1990. Incremental evaluation of computational circuits. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. 32--42."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740822"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496890"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics","author":"Cherkassky Boris V.","year":"1997","unstructured":"Boris V. Cherkassky , Andrew V. Goldberg , and Craig Silverstein . 1997 . Buckets, heaps, lists, and monotone priority queues . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, 83--92. Boris V. Cherkassky, Andrew V. Goldberg, and Craig Silverstein. 1997. Buckets, heaps, lists, and monotone priority queues. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 83--92."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.1.161"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28434"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_35"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071382"},{"key":"e_1_2_1_12_1","volume-title":"Structural Models: An Introduction to the Theory of Directed Graphs","author":"Harary Frank","year":"1965","unstructured":"Frank Harary , Robert Z. Norman , and Dorwin Cartwright . 1965 . Structural Models: An Introduction to the Theory of Directed Graphs . John Wiley & Sons . Frank Harary, Robert Z. Norman, and Dorwin Cartwright. 1965. Structural Models: An Introduction to the Theory of Directed Graphs. John Wiley & Sons."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/368996.369025"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms","author":"Katriel Irit","unstructured":"Irit Katriel and Hans L. Bodlaender . 2005. Online topological ordering . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms . Vancouver, British Columbia, Canada, 443--450. Irit Katriel and Hans L. Bodlaender. 2005. Online topological ordering. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. Vancouver, British Columbia, Canada, 443--450."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159896"},{"key":"e_1_2_1_17_1","volume-title":"The Art of Computer Programming, Volume 1: Fundamental Algorithms","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1973. The Art of Computer Programming, Volume 1: Fundamental Algorithms ( 2 nd ed.). Addison Wesley , Reading, MA . Donald E. Knuth. 1973. The Art of Computer Programming, Volume 1: Fundamental Algorithms (2nd ed.). Addison Wesley, Reading, MA.","edition":"2"},{"key":"e_1_2_1_18_1","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1998. The Art of Computer Programming, Volume 3: Sorting and Searching ( 2 nd ed.). Addison Wesley Longman Publishing Co. , Redwood City, CA, USA . Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison Wesley Longman Publishing Co., Redwood City, CA, USA.","edition":"2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90001-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.08.009"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00075-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCAM.2003.1238026"},{"key":"e_1_2_1_24_1","volume-title":"Kelly","author":"Pearce David J.","year":"2003","unstructured":"David J. Pearce and Paul H. J . Kelly . 2003 . Online Algorithms for Topological Order and Strongly Connected Components. Technical Report. Imperial College , London. David J. Pearce and Paul H. J. Kelly. 2003. Online Algorithms for Topological Order and Strongly Connected Components. Technical Report. Imperial College, London."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 3rd International Workshop on Efficient Experimental Algorithms (Lecture Notes in Computer Science)","volume":"3059","author":"David","unstructured":"David J. Pearce and Paul H. J. Kelly. 2004. A dynamic algorithm for topologically sorting directed acyclic graphs . In Proceedings of the 3rd International Workshop on Efficient Experimental Algorithms (Lecture Notes in Computer Science) , Vol. 3059 . Springer, 383--398. David J. Pearce and Paul H. J. Kelly. 2004. A dynamic algorithm for topologically sorting directed acyclic graphs. In Proceedings of the 3rd International Workshop on Efficient Experimental Algorithms (Lecture Notes in Computer Science), Vol. 3059. Springer, 383--398."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1210590"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 33rd Australasian Conference on Computer Science (ACSC\u201910)","author":"David","unstructured":"David J. Pearce and Paul H. J. Kelly. 2010. A batch algorithm for maintaining a topological order . In Proceedings of the 33rd Australasian Conference on Computer Science (ACSC\u201910) . 79--88. David J. Pearce and Paul H. J. Kelly. 2010. A batch algorithm for maintaining a topological order. In Proceedings of the 33rd Australasian Conference on Computer Science (ACSC\u201910). 79--88."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/060650271"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-16-1-386-389"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203006"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_33_1","volume-title":"Data Structures and Network Algorithms","author":"Tarjan Robert Endre","unstructured":"Robert Endre Tarjan . 1983. Data Structures and Network Algorithms . Society for Industrial and Applied Mathematics , Philadelphia, PA . Robert Endre Tarjan. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","article-title":"Algorithm 232","volume":"7","author":"Williams J. W. J.","year":"1964","unstructured":"J. W. J. Williams . 1964 . Algorithm 232 : Heapsort. Communications of the ACM 7 , 6 (1964), 347 -- 348 . J. W. J. Williams. 1964. Algorithm 232: Heapsort. Communications of the ACM 7, 6 (1964), 347--348.","journal-title":"Heapsort. Communications of the ACM"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2756553","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2756553","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:26Z","timestamp":1750227146000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2756553"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,8]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2756553"],"URL":"https:\/\/doi.org\/10.1145\/2756553","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,8]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}