{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T22:00:51Z","timestamp":1767650451951},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540220671"},{"type":"electronic","value":"9783540248385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24838-5_29","type":"book-chapter","created":{"date-parts":[[2010,8,8]],"date-time":"2010-08-08T17:34:14Z","timestamp":1281288854000},"page":"383-398","source":"Crossref","is-referenced-by-count":8,"title":["A Dynamic Algorithm for Topologically Sorting Directed Acyclic Graphs"],"prefix":"10.1007","author":[{"given":"David J.","family":"Pearce","sequence":"first","affiliation":[]},{"given":"Paul H. J.","family":"Kelly","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","unstructured":"Alpern, B., Hoover, R., Rosen, B.K., Sweeney, P.F., Zadeck, F.K.: Incremental evaluation of computational circuits. In: Proc. 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 32\u201342 (1990)"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Baswana, S., Hariharan, R., Sen, S.: Improved algorithms for maintaining transitive closure and all-pairs shortest paths in digraphs under edge deletions. In: Proc. ACM Symposium on Theory of Computing (2002)","DOI":"10.1145\/509927.509928"},{"key":"29_CR3","unstructured":"Berman, A.M.: Lower And Upper Bounds For Incremental Algorithms. PhD thesis, New Brunswick, New Jersey (1992)"},{"key":"29_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study. In: Proc. Workshop on Algorithm Engineering. LNCS, pp. 218\u2013229 (2000)","DOI":"10.1007\/3-540-44691-5_19"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: Fully dynamic transitive closure: breaking through the O(n2) barrier. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 381\u2013389 (2000)","DOI":"10.1109\/SFCS.2000.892126"},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"Dietz, P., Sleator, D.: Two algorithms for maintaining order in a list. In: Proc. ACM Symposium on Theory of Computing, pp. 365\u2013372 (1987)","DOI":"10.1145\/28395.28434"},{"issue":"4","key":"29_CR8","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s004530010043","volume":"28","author":"H. Djidjev","year":"2000","unstructured":"Djidjev, H., Pantziou, G.E., Zaroliagis, C.D.: Improved algorithms for dynamic shortest paths. Algorithmica\u00a028(4), 367\u2013389 (2000)","journal-title":"Algorithmica"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic shortest paths and negative cycle detection on digraphs with arbitrary arc weights. In: Proc. European Symposium on Algorithms, pp. 320\u2013331 (1998)","DOI":"10.1007\/3-540-68530-8_27"},{"issue":"3","key":"29_CR10","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1145\/155271.155273","volume":"18","author":"Y. Ioannidis","year":"1993","unstructured":"Ioannidis, Y., Ramakrishnan, R., Winger, L.: Transitive closure algorithms based on graph traversal. ACM Transactions on Database Systems\u00a018(3), 512\u2013576 (1993)","journal-title":"ACM Transactions on Database Systems"},{"key":"29_CR11","volume-title":"Algorithms and Theory of Computation Handbook","author":"G.F. Italiano","year":"1999","unstructured":"Italiano, G.F., Eppstein, D., Galil, Z.: Dynamic graph algorithms. In: Algorithms and Theory of Computation Handbook, CRC Press, Boca Raton (1999)"},{"issue":"1","key":"29_CR12","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1002\/rsa.3240010106","volume":"1","author":"R.M. Karp","year":"1990","unstructured":"Karp, R.M.: The transitive closure of a random digraph. Random Structures & Algorithms\u00a01(1), 73\u201394 (1990)","journal-title":"Random Structures & Algorithms"},{"key":"29_CR13","unstructured":"Katriel, I.: On algorithms for online topological ordering and sorting. Research Report MPI-I-2004-1-003, Max-Planck-Institut f\u00fcr Informatik (2004)"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"King, V., Sagert, G.: A fully dynamic algorithm for maintaining the transitive closure. In: Proc. ACM Symposium on Theory of Computing, pp. 492\u2013498 (1999)","DOI":"10.1145\/301250.301380"},{"issue":"1","key":"29_CR15","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(96)00075-0","volume":"59","author":"A. Marchetti-Spaccamela","year":"1996","unstructured":"Marchetti-Spaccamela, A., Nanni, U., Rohnert, H.: Maintaining a topological order under edge insertions. Information Processing Letters\u00a059(1), 53\u201358 (1996)","journal-title":"Information Processing Letters"},{"key":"29_CR16","unstructured":"Pearce, D.J.: Some directed graph algorithms and their application to pointer analysis. PhD thesis, Imperial College, London (2004) (work in progress)"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Pearce, D.J., Kelly, P.H.J., Hankin, C.: Online cycle detection and difference propagation for pointer analysis. In: Proc. IEEE workshop on Source Code Analysis and Manipulation (2003)","DOI":"10.1109\/SCAM.2003.1238026"},{"key":"29_CR18","series-title":"Lecture Notes in Computer Science","volume-title":"Bounded Incremental Computation","year":"1996","unstructured":"Ramalingam, G. (ed.): Bounded Incremental Computation. LNCS, vol.\u00a01089. Springer, Heidelberg (1996)"},{"issue":"3","key":"29_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0020-0190(94)00080-8","volume":"51","author":"G. Ramalingam","year":"1994","unstructured":"Ramalingam, G., Reps, T.: On competitive on-line algorithms for the dynamic priority-ordering problem. Information Processing Letters\u00a051(3), 155\u2013161 (1994)","journal-title":"Information Processing Letters"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Reps, T.: Optimal-time incremental semantic analysis for syntax-directed editors. In: Proc. Symp. on Principles of Programming Languages, pp. 169\u2013176 (1982)","DOI":"10.1145\/582153.582172"},{"issue":"4","key":"29_CR21","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.ipl.2003.07.005","volume":"88","author":"J. Zhou","year":"2003","unstructured":"Zhou, J., M\u00fcller, M.: Depth-first discovery algorithm for incremental topological sorting of directed acyclic graphs. Information Processing Letters\u00a088(4), 195\u2013200 (2003)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24838-5_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:56:52Z","timestamp":1605743812000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24838-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540220671","9783540248385"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24838-5_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}