{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:24:25Z","timestamp":1776864265495,"version":"3.51.2"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0830676CCF-0832797"],"award-info":[{"award-number":["CCF-0830676CCF-0832797"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>\n            We present two online algorithms for maintaining a topological order of a directed\n            <jats:italic>n<\/jats:italic>\n            -vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles\n            <jats:italic>m<\/jats:italic>\n            arc additions in O(\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) time. For sparse graphs (\n            <jats:italic>m<\/jats:italic>\n            \/\n            <jats:italic>n<\/jats:italic>\n            = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>5\/2<\/jats:sup>\n            ) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            2\n            <jats:sup>\u221a2 lg<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time by relating its performance to a generalization of the\n            <jats:italic>k<\/jats:italic>\n            -levels problem of combinatorial geometry. A completely different algorithm running in \u0398(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.\n          <\/jats:p>","DOI":"10.1145\/2071379.2071382","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T16:47:14Z","timestamp":1327423634000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":44,"title":["Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance"],"prefix":"10.1145","volume":"8","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Telikepalli","family":"Kavitha","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rogers","family":"Mathew","sequence":"additional","affiliation":[{"name":"Indian Institute of Science"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddhartha","family":"Sen","sequence":"additional","affiliation":[{"name":"Princeton University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton University &amp; HP Laboratories"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1983. Data Structures and Algorithms. Addison-Wesley. Aho A. V. Hopcroft J. E. and Ullman J. D. 1983. Data Structures and Algorithms . Addison-Wesley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785293_8"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA). 32--42","author":"Alpern B.","unstructured":"Alpern , B. , Hoover , R. , Rosen , B. K. , Sweeney , P. F. , and Zadeck , F. K . 1990. Incremental evaluation of computational circuits . In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA). 32--42 . Alpern, B., Hoover, R., Rosen, B. K., Sweeney, P. F., and Zadeck, F. K. 1990. Incremental evaluation of computational circuits. In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA). 32--42."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.55690"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 10th European Symposium on Algorithms (ESA). 152--164","author":"Bender M. A.","unstructured":"Bender , M. A. , Cole , R. , Demaine , E. D. , Farach-Colton , M. , and Zito , J . 2002. Two simplified algorithms for maintaining order in a list . In Proceedings of the 10th European Symposium on Algorithms (ESA). 152--164 . Bender, M. A., Cole, R., Demaine, E. D., Farach-Colton, M., and Zito, J. 2002. Two simplified algorithms for maintaining order in a list. In Proceedings of the 10th European Symposium on Algorithms (ESA). 152--164."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1108--1115","author":"Bender M. A.","unstructured":"Bender , M. A. , Fineman , J. T. , and Gilbert , S . 2009. A new approach to incremental topological ordering . In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1108--1115 . Bender, M. A., Fineman, J. T., and Gilbert, S. 2009. A new approach to incremental topological ordering. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1108--1115."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940880"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009354"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28434"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288611"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00051-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_35"},{"key":"e_1_2_1_15_1","unstructured":"Haeupler B. Sen S. and Tarjan R. E. 2008b. Incremental topological ordering and strong component maintenance. http:\/\/arxiv.org\/abs\/0803.0792. Haeupler B. Sen S. and Tarjan R. E. 2008b. Incremental topological ordering and strong component maintenance. http:\/\/arxiv.org\/abs\/0803.0792."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). 135--144","author":"Han Y.","unstructured":"Han , Y. and Thorup , M . 2002. Integer sorting in O(n\u221alog log n) expected time and linear space . In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). 135--144 . Han, Y. and Thorup, M. 2002. Integer sorting in O(n\u221alog log n) expected time and linear space. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). 135--144."},{"key":"e_1_2_1_17_1","unstructured":"Harary F. Norman R. Z. and Cartwright D. 1965. Structural Models : An Introduction to the Theory of Directed Graphs. Wiley. Harary F. Norman R. Z. and Cartwright D. 1965. Structural Models : An Introduction to the Theory of Directed Graphs . Wiley."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366647"},{"key":"e_1_2_1_19_1","volume-title":"On algorithms for online topological ordering and sorting. Tech. rep. MPI-I-2004-1-003","author":"Katriel I.","unstructured":"Katriel , I. 2004. On algorithms for online topological ordering and sorting. Tech. rep. MPI-I-2004-1-003 , Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany . Katriel, I. 2004. On algorithms for online topological ordering and sorting. Tech. rep. MPI-I-2004-1-003, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159896"},{"key":"e_1_2_1_21_1","unstructured":"Kavitha T. and Mathew R. 2007. Faster algorithms for online topological ordering. http:\/\/arxiv.org\/abs\/0711.0251. Kavitha T. and Mathew R. 2007. Faster algorithms for online topological ordering. http:\/\/arxiv.org\/abs\/0711.0251."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IFIP Congress. 19--27","author":"Knuth D. E.","year":"1972","unstructured":"Knuth , D. E. 1972 . Mathematical analysis of algorithms . In Proceedings of the IFIP Congress. 19--27 . Knuth, D. E. 1972. Mathematical analysis of algorithms. In Proceedings of the IFIP Congress. 19--27."},{"key":"e_1_2_1_23_1","volume-title":"Fundamental Algorithms","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1973. The Art of Computer Programming . Vol. 1 : Fundamental Algorithms . Addison-Wesley . Knuth, D. E. 1973. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. Addison-Wesley."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90001-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.08.009"},{"key":"e_1_2_1_26_1","volume-title":"-M","author":"Liu H.-F.","year":"2008","unstructured":"Liu , H.-F. and Chao , K . -M . 2008 . An \u00d5(n 2.5)-time algorithm for online topological ordering. http:\/\/arxiv.org\/abs\/0804.3860. Liu, H.-F. and Chao, K.-M. 2008. An \u00d5(n 2.5)-time algorithm for online topological ordering. http:\/\/arxiv.org\/abs\/0804.3860."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 70--86","author":"Marchetti-Spaccamela A.","unstructured":"Marchetti-Spaccamela , A. , Nanni , U. , and Rohnert , H . 1993. On-line graph algorithms for incremental compilation . In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 70--86 . Marchetti-Spaccamela, A., Nanni, U., and Rohnert, H. 1993. On-line graph algorithms for incremental compilation. In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 70--86."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00075-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Nivasch G. 2008. An improved simple construction of many halving edges. In Surveys on Discrete and Computational Geometry: Twenty Years Later. AMS 299--305. Nivasch G. 2008. An improved simple construction of many halving edges. In Surveys on Discrete and Computational Geometry: Twenty Years Later . AMS 299--305.","DOI":"10.1090\/conm\/453\/08804"},{"key":"e_1_2_1_30_1","unstructured":"Omohundro S. M. Lim C.-C. and Bilmes J. 1992. The Sather language compiler\/debugger implementation. Tech. rep. TR-92-017 International Computer Science Institute Berkeley. Omohundro S. M. Lim C.-C. and Bilmes J. 1992. The Sather language compiler\/debugger implementation. Tech. rep. TR-92-017 International Computer Science Institute Berkeley."},{"key":"e_1_2_1_32_1","unstructured":"Pearce D. J. and Kelly P. H. J. 2003. Online algorithms for topological order and strongly connected components. http:\/\/homepages.ecs.vuw.ac.nz\/~djp\/files\/tr0903.pdf. Pearce D. J. and Kelly P. H. J. 2003. Online algorithms for topological order and strongly connected components. http:\/\/homepages.ecs.vuw.ac.nz\/~djp\/files\/tr0903.pdf."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1210590"},{"key":"e_1_2_1_34_1","unstructured":"Pearce D. J. and Kelly P. H. J. 2007. A dynamic batch algorithm for maintaining a topological order. Tech. rep. Victoria University Wellington New Zealand. Pearce D. J. and Kelly P. H. J. 2007. A dynamic batch algorithm for maintaining a topological order. Tech. rep. Victoria University Wellington New Zealand."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE Workshop on Source Code Analysis and Manipulation (SCAM). 3--12","author":"Pearce D. J.","unstructured":"Pearce , D. J. , Kelly , P. H. J. , and Hankin , C . 2003. Online cycle detection and difference propagation for pointer analysis . In Proceedings of the IEEE Workshop on Source Code Analysis and Manipulation (SCAM). 3--12 . Pearce, D. J., Kelly, P. H. J., and Hankin, C. 2003. Online cycle detection and difference propagation for pointer analysis. In Proceedings of the IEEE Workshop on Source Code Analysis and Manipulation (SCAM). 3--12."},{"key":"e_1_2_1_36_1","unstructured":"Ramalingam G. and Reps T. W. 1991. On the computational complexity of incremental algorithms. Tech. rep. CS-TR-1991-1033 University of Wisconsin-Madison. Ramalingam G. and Reps T. W. 1991. On the computational complexity of incremental algorithms. Tech. rep. CS-TR-1991-1033 University of Wisconsin-Madison."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00080-8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/060650271"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80029-3"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90008-0"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS). 127--139","author":"Sharir M.","unstructured":"Sharir , M. and Smorodinsky , S . 2003. Extremal configurations and levels in pseudoline arrangements . In Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS). 127--139 . Sharir, M. and Smorodinsky, S. 2003. Extremal configurations and levels in pseudoline arrangements. In Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS). 127--139."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90038-8"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-16-1-386-389"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0999-9"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.003"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010022"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071382","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2071379.2071382","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:22Z","timestamp":1750241182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071382"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2071379.2071382"],"URL":"https:\/\/doi.org\/10.1145\/2071379.2071382","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}