{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T05:57:04Z","timestamp":1763704624818,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T00:00:00Z","timestamp":1170979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2007,2,9]]},"abstract":"<jats:p>We consider the problem of maintaining the topological order of a directed acyclic graph (DAG) in the presence of edge insertions and deletions. We present a new algorithm and, although this has inferior time complexity compared with the best previously known result, we find that its simplicity leads to better performance in practice. In addition, we provide an empirical comparison against the three main alternatives over a large number of random DAGs. The results show our algorithm is the best for sparse digraphs and only a constant factor slower than the best on dense digraphs.<\/jats:p>","DOI":"10.1145\/1187436.1210590","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":34,"title":["A dynamic topological sort algorithm for directed acyclic graphs"],"prefix":"10.1145","volume":"11","author":[{"given":"David J.","family":"Pearce","sequence":"first","affiliation":[{"name":"Victoria University of Wellington, Wellington, New Zealand"}]},{"given":"Paul H. J.","family":"Kelly","sequence":"additional","affiliation":[{"name":"Imperial College London, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2007,2,9]]},"reference":[{"volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC). 171--180","author":"Aiello W.","key":"e_1_2_2_1_1","unstructured":"Aiello , W. , Chung , F. , and Lu , L . 2000. A random graph model for power law graphs . In Proceedings of the ACM Symposium on the Theory of Computing (STOC). 171--180 .]] 10.1145\/335305.335326 Aiello, W., Chung, F., and Lu, L. 2000. A random graph model for power law graphs. In Proceedings of the ACM Symposium on the Theory of Computing (STOC). 171--180.]] 10.1145\/335305.335326"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science","volume":"4059","author":"Ajwani D.","unstructured":"Ajwani , D. , Friedrich , T. , and Meyer , U . 2006. An O(n2.75) algorithm for online topological ordering . In Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science , vol. 4059 . Springer-Verlag, New York. 53--74.]] 10.1007\/11785293_8 Ajwani, D., Friedrich, T., and Meyer, U. 2006. An O(n2.75) algorithm for online topological ordering. In Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 4059. Springer-Verlag, New York. 53--74.]] 10.1007\/11785293_8"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM Press","author":"Alpern B.","key":"e_1_2_2_3_1","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 ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM Press , New York. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM Press, New York. 32--42.]]"},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Barak A. and Erd\u00f6s P. 1984. On the maximal number of strongly independent vertices in a random acyclic directed graph. 5 4 508--514.]]  Barak A. and Erd\u00f6s P. 1984. On the maximal number of strongly independent vertices in a random acyclic directed graph. 5 4 508--514.]]","DOI":"10.1137\/0605049"},{"volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press","author":"Baswana S.","key":"e_1_2_2_5_1","unstructured":"Baswana , S. , Hariharan , R. , and Sen , S . 2002. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths in digraphs under edge deletions . In Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press , New York. 117--123.]] 10.1145\/509907.509928 Baswana, S., Hariharan, R., and Sen, S. 2002. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths in digraphs under edge deletions. In Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press, New York. 117--123.]] 10.1145\/509907.509928"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science","volume":"2461","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 European Symposium on Algorithms (ESA). Lecture Notes in Computer Science , vol. 2461 . Springer-Verlag, New York. 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 European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2461. Springer-Verlag, New York. 152--164.]]"},{"key":"e_1_2_2_8_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. MIT Press Cambridge MA.]]   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. MIT Press Cambridge MA.]]"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Demetrescu C.","key":"e_1_2_2_9_1","unstructured":"Demetrescu , C. and Italiano , G. F . 2000. Fully dynamic transitive closure: breaking through the O(n2) barrier . In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Washington, DC. 381--389.]] Demetrescu, C. and Italiano, G. F. 2000. Fully dynamic transitive closure: breaking through the O(n2) barrier. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Washington, DC. 381--389.]]"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the Workshop on Algorithm Engineering (WAE). Lecture Notes in Computer Science","volume":"1982","author":"Demetrescu C.","unstructured":"Demetrescu , C. , Frigioni , D. , Marchetti-Spaccamela , A. , and Nanni , U . 2000. Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study . In Proceedings of the Workshop on Algorithm Engineering (WAE). Lecture Notes in Computer Science , vol. 1982 . Springer-Verlag, New York. 218--229.]] Demetrescu, C., Frigioni, D., Marchetti-Spaccamela, A., and Nanni, U. 2000. Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study. In Proceedings of the Workshop on Algorithm Engineering (WAE). Lecture Notes in Computer Science, vol. 1982. Springer-Verlag, New York. 218--229.]]"},{"volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press","author":"Dietz P. F.","key":"e_1_2_2_11_1","unstructured":"Dietz , P. F. and Sleator , D. D . 1987. Two algorithms for maintaining order in a list . In Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press , New York. 365--372.]] 10.1145\/28395.28434 Dietz, P. F. and Sleator, D. D. 1987. Two algorithms for maintaining order in a list. In Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press, New York. 365--372.]] 10.1145\/28395.28434"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s004530010043","article-title":"Improved algorithms for dynamic shortest paths","volume":"28","author":"Djidjev H.","year":"2000","unstructured":"Djidjev , H. , Pantziou , G. E. , and Zaroliagis , C. D. 2000 . Improved algorithms for dynamic shortest paths . Algorithmica 28 , 4, 367 -- 389 .]] Djidjev, H., Pantziou, G. E., and Zaroliagis, C. D. 2000. Improved algorithms for dynamic shortest paths. Algorithmica 28, 4, 367--389.]]","journal-title":"Algorithmica"},{"key":"e_1_2_2_13_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u00f6s P.","year":"1960","unstructured":"Erd\u00f6s , P. and R\u00e9nyi , A. 1960 . On the evolution of random graphs . Mathematical Institute of the Hungarian Academy of Sciences 5 , 17 -- 61 .]] Erd\u00f6s, P. and R\u00e9nyi, A. 1960. On the evolution of random graphs. Mathematical Institute of the Hungarian Academy of Sciences 5, 17--61.]]","journal-title":"Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Lecture Notes in Computer Science","volume":"880","author":"Frigioni D.","unstructured":"Frigioni , D. , Marchetti-Spaccamela , A. , and Nanni , U . 1994. Incremental algorithms for the single-source shortest path problem . In Proceedings of the conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Lecture Notes in Computer Science , vol. 880 . Springer-Verlag, New York. 113--124.]] Frigioni, D., Marchetti-Spaccamela, A., and Nanni, U. 1994. Incremental algorithms for the single-source shortest path problem. In Proceedings of the conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Lecture Notes in Computer Science, vol. 880. Springer-Verlag, New York. 113--124.]]"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science","volume":"1461","author":"Frigioni D.","unstructured":"Frigioni , D. , Marchetti-Spaccamela , A. , and Nanni , U . 1998. Fully dynamic shortest paths and negative cycles detection on digraphs with arbitrary arc weights . In Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science , vol. 1461 . Springer-Verlag, New York. 320--331.]] Frigioni, D., Marchetti-Spaccamela, A., and Nanni, U. 1998. Fully dynamic shortest paths and negative cycles detection on digraphs with arbitrary arc weights. In Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 1461. Springer-Verlag, New York. 320--331.]]"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the Brazillian Symposium on Artificial Intelligence (SBIA).","volume":"2507","author":"Ide J. S.","unstructured":"Ide , J. S. and Cozman , F. G . 2002. Random generation of bayesian networks . In Proceedings of the Brazillian Symposium on Artificial Intelligence (SBIA). Vol. 2507 . Springer-Verlag, New York. 366--375.]] Ide, J. S. and Cozman, F. G. 2002. Random generation of bayesian networks. In Proceedings of the Brazillian Symposium on Artificial Intelligence (SBIA). Vol. 2507. Springer-Verlag, New York. 366--375.]]"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Italiano G. F. Eppstein D. and Galil Z. 1999. Dynamic graph algorithms. In Handbook of Algorithms and Theory of Computation Chapter 22. CRC Press Boca Raton FL.]]  Italiano G. F. Eppstein D. and Galil Z. 1999. Dynamic graph algorithms. In Handbook of Algorithms and Theory of Computation Chapter 22. CRC Press Boca Raton FL.]]","DOI":"10.1201\/9781420049503-c9"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Janson S. Luczak T. and Rucinski A. 2000. Random Graphs. Wiley New York.]]  Janson S. Luczak T. and Rucinski A. 2000. Random Graphs. Wiley New York.]]","DOI":"10.1002\/9781118032718"},{"volume-title":"Online topological ordering and sorting. Tech. rep","author":"Katriel I.","key":"e_1_2_2_20_1","unstructured":"Katriel , I. 2004. Online topological ordering and sorting. Tech. rep ., Max-Planck-Institut f\u00fcr Informatik .]] Katriel, I. 2004. Online topological ordering and sorting. Tech. rep., Max-Planck-Institut f\u00fcr Informatik.]]"},{"volume-title":"Proceedings of the ACM Symposium on Discrete Algorithms (SODA). ACM Press","author":"Katriel I.","key":"e_1_2_2_21_1","unstructured":"Katriel , I. and Bodlaender , H. L . 2005. Online topological ordering . In Proceedings of the ACM Symposium on Discrete Algorithms (SODA). ACM Press , New York. 443--450.]] Katriel, I. and Bodlaender, H. L. 2005. Online topological ordering. In Proceedings of the ACM Symposium on Discrete Algorithms (SODA). ACM Press, New York. 443--450.]]"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-005-0554-9"},{"volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press","author":"King V.","key":"e_1_2_2_23_1","unstructured":"King , V. and Sagert , G . 1999. A fully dynamic algorithm for maintaining the transitive closure . In Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press , New York. 492--498.]] 10.1145\/301250.301380 King, V. and Sagert, G. 1999. A fully dynamic algorithm for maintaining the transitive closure. In Proceedings of the ACM Symposium on Theory of Computing (STOC). ACM Press, New York. 492--498.]] 10.1145\/301250.301380"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00075-0"},{"volume-title":"Proceedings of the Euroconference on Combinatorics, Graph Theory and Applications (COMB)","author":"Mela\u00e7con G.","key":"e_1_2_2_25_1","unstructured":"Mela\u00e7con , G. , Bousquet-Melou , M. , and Dutor , I . 2001. Random generation of directed acyclic graphs . In Proceedings of the Euroconference on Combinatorics, Graph Theory and Applications (COMB) . Elsevier Science, New York. 12--15.]] Mela\u00e7con, G., Bousquet-Melou, M., and Dutor, I. 2001. Random generation of directed acyclic graphs. In Proceedings of the Euroconference on Combinatorics, Graph Theory and Applications (COMB). Elsevier Science, New York. 12--15.]]"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the Workshop on Efficient and experimental Algorithms (WEA). Lecture Notes in Computer Science","volume":"3059","author":"Pearce D. J.","unstructured":"Pearce , D. J. and Kelly , P. H. J. 2004. A dynamic algorithm for topologically sorting directed acyclic graphs . In Proceedings of the Workshop on Efficient and experimental Algorithms (WEA). Lecture Notes in Computer Science , vol. 3059 . Springer-Verlag, New York. 383--398.]] Pearce, D. J. and Kelly, P. H. J. 2004. A dynamic algorithm for topologically sorting directed acyclic graphs. In Proceedings of the Workshop on Efficient and experimental Algorithms (WEA). Lecture Notes in Computer Science, vol. 3059. Springer-Verlag, New York. 383--398.]]"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:SQJO.0000039791.93071.a2"},{"key":"e_1_2_2_29_1","first-page":"164","article-title":"A phase transition phenomenon in a random directed acyclic graph","volume":"18","author":"Pittel B.","year":"2001","unstructured":"Pittel , B. and Tungol , R. 2001 . A phase transition phenomenon in a random directed acyclic graph . RSA: Random Structures & Algorithms 18 , 2, 164 -- 184 .]] Pittel, B. and Tungol, R. 2001. A phase transition phenomenon in a random directed acyclic graph. RSA: Random Structures & Algorithms 18, 2, 164--184.]]","journal-title":"RSA: Random Structures & Algorithms"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00080-8"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the ACM Symposium on Principles of Programming Languages (POPL). ACM Press","author":"Reps T.","year":"1982","unstructured":"Reps , T. 1982 . Optimal-time incremental semantic analysis for syntax-directed editors . In Proceedings of the ACM Symposium on Principles of Programming Languages (POPL). ACM Press , New York. 169--176.]] 10.1145\/582153.582172 Reps, T. 1982. Optimal-time incremental semantic analysis for syntax-directed editors. In Proceedings of the ACM Symposium on Principles of Programming Languages (POPL). ACM Press, New York. 169--176.]] 10.1145\/582153.582172"},{"volume-title":"Proceedings of the ACM Symposium on the Principles of Programming Languages (POPL). ACM Press","author":"Reps T.","key":"e_1_2_2_34_1","unstructured":"Reps , T. , Marceau , C. , and Teitelbaum , T . 1986. Remote attribute updating for language-based editors . In Proceedings of the ACM Symposium on the Principles of Programming Languages (POPL). ACM Press , New York. 1--13.]] 10.1145\/512644.512645 Reps, T., Marceau, C., and Teitelbaum, T. 1986. Remote attribute updating for language-based editors. In Proceedings of the ACM Symposium on the Principles of Programming Languages (POPL). ACM Press, New York. 1--13.]] 10.1145\/512644.512645"},{"key":"e_1_2_2_35_1","unstructured":"Siek J. Lee L.-Q. and Lumsdaine A. 2002. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Reading MA.]]   Siek J. Lee L.-Q. and Lumsdaine A. 2002. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Reading MA.]]"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the Twente Workshop on Language Technology (TWLT)","author":"Wirn M.","year":"1993","unstructured":"Wirn , M. 1993 . Bounded incremental parsing . In Proceedings of the Twente Workshop on Language Technology (TWLT) . University of Twente, University of Twente, Enschede, The Netherlands. 145--156.]] Wirn, M. 1993. Bounded incremental parsing. In Proceedings of the Twente Workshop on Language Technology (TWLT). University of Twente, University of Twente, Enschede, The Netherlands. 145--156.]]"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1007\/BF01934460","article-title":"On incremental evaluation of ordered attributed grammars","volume":"23","author":"Yeh D.","year":"1983","unstructured":"Yeh , D. 1983 . On incremental evaluation of ordered attributed grammars . BIT 23 , 308 -- 320 .]] Yeh, D. 1983. On incremental evaluation of ordered attributed grammars. BIT 23, 308--320.]]","journal-title":"BIT"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j\/ipl.2003.07.005"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1210590","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187436.1210590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:11Z","timestamp":1750262891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1210590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,9]]},"references-count":34,"alternative-id":["10.1145\/1187436.1210590"],"URL":"https:\/\/doi.org\/10.1145\/1187436.1210590","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2007,2,9]]}}}