{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:24:24Z","timestamp":1776864264849,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705741","type":"print"},{"value":"9783540705758","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_35","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"421-433","source":"Crossref","is-referenced-by-count":13,"title":["Faster Algorithms for Incremental Topological Ordering"],"prefix":"10.1007","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Telikepalli","family":"Kavitha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rogers","family":"Mathew","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddhartha","family":"Sen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/11785293_8","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"D. Ajwani","year":"2006","unstructured":"Ajwani, D., Friedrich, T., Meyer, U.: An O(n 2.75) algorithm for online topological ordering. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 53\u201364. Springer, Heidelberg (2006)"},{"key":"35_CR2","unstructured":"Alpern, B., Hoover, R., Rosen, B.K., Sweeney, P.F., Zadeck, F.K.: Incremental evaluation of computational circuits. In: SODA 1990, pp. 32\u201342 (1990)"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"Belik, F.: An efficient deadlock avoidance technique. IEEE Trans. on Comput.\u00a039(7) (1990)","DOI":"10.1109\/12.55690"},{"key":"35_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/3-540-45749-6_17","volume-title":"Algorithms - ESA 2002","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 152\u2013164. Springer, Heidelberg (2002)"},{"issue":"4","key":"35_CR5","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. of Comput. and Syst. Sci.\u00a07(4), 448\u2013461 (1973)","journal-title":"J. of Comput. and Syst. Sci."},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"Dietz, P.F., Sleator, D.D.: Two algorithms for maintaining order in a list. In: STOC 1987, pp. 365\u2013372 (1987)","DOI":"10.1145\/28395.28434"},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Sen, S., Tarjan, R.E.: Incremental topological ordering and strong component maintenance (2008)","DOI":"10.1007\/978-3-540-70575-8_35"},{"key":"35_CR8","unstructured":"Han, Y., Thorup, M.: Integer sorting in O(n $\\sqrt{\\log \\log n}$) expected time and linear space. In: FOCS 2002, pp. 135\u2013144 (2002)"},{"key":"35_CR9","volume-title":"Structural Models\u00a0: An Introduction to the Theory of Directed Graphs","author":"F. Harary","year":"1965","unstructured":"Harary, F., Norman, R.Z., Cartwright, D.: Structural Models\u00a0: An Introduction to the Theory of Directed Graphs. John Wiley & Sons, Chichester (1965)"},{"key":"35_CR10","unstructured":"Katriel, I.: On algorithms for online topological ordering and sorting. Technical Report MPI-I-2004-1-003, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany (2004)"},{"issue":"3","key":"35_CR11","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1145\/1159892.1159896","volume":"2","author":"I. Katriel","year":"2006","unstructured":"Katriel, I., Bodlaender, H.L.: Online topological ordering. ACM Trans. on Algor.\u00a02(3), 364\u2013379 (2006)","journal-title":"ACM Trans. on Algor."},{"key":"35_CR12","unstructured":"Kavitha, T., Mathew, R.: Faster algorithms for online topological ordering (2007)"},{"key":"35_CR13","series-title":"Fundamental Algorithms","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming. Fundamental Algorithms, vol.\u00a01. Addison-Wesley, Reading (1973)"},{"issue":"6","key":"35_CR14","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(74)90001-5","volume":"2","author":"D.E. Knuth","year":"1974","unstructured":"Knuth, D.E., Szwarcfiter, J.L.: A structured program to generate all topological sorting arrangements. Inf. Proc. Lett.\u00a02(6), 153\u2013157 (1974)","journal-title":"Inf. Proc. Lett."},{"issue":"1-2","key":"35_CR15","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/j.tcs.2007.08.009","volume":"389","author":"H.-F. Liu","year":"2007","unstructured":"Liu, H.-F., Chao, K.-M.: A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering. Theor. Comput. Sci.\u00a0389(1-2), 182\u2013189 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"35_CR16","unstructured":"Liu, H.-F., Chao, K.-M.: An \u00d5(n 2.5)-time algorithm for online topological ordering (2008)"},{"key":"35_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-57899-4_42","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Marchetti-Spaccamela","year":"1994","unstructured":"Marchetti-Spaccamela, A., Nanni, U., Rohnert, H.: On-line graph algorithms for incremental compilation. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol.\u00a0790, pp. 70\u201386. Springer, Heidelberg (1994)"},{"issue":"1","key":"35_CR18","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. Inf. Proc. Lett.\u00a059(1), 53\u201358 (1996)","journal-title":"Inf. Proc. Lett."},{"key":"35_CR19","unstructured":"Omohundro, S.M., Lim, C.-C., Bilmes, J.: The Sather language compiler\/debugger implementation. Technical Report TR-92-017, International Computer Science Institute, Berkeley (1992)"},{"key":"35_CR20","first-page":"1","volume":"11","author":"D.J. Pearce","year":"2006","unstructured":"Pearce, D.J., Kelly, P.H.J.: A dynamic topological sort algorithm for directed acyclic graphs. J. of Exp. Algorithmics\u00a011, 1\u20137 (2006)","journal-title":"J. of Exp. Algorithmics"},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"Pearce, D.J., Kelly, P.H.J., Hankin, C.: Online cycle detection and difference propagation for pointer analysis. In: SCAM 2003, pp. 3\u201312 (2003)","DOI":"10.1023\/B:SQJO.0000039791.93071.a2"},{"key":"35_CR22","unstructured":"Ramalingam, G., Reps, T.W.: On the computational complexity of incremental algorithms. Technical Report CS-TR-1991-1033, University of Wisconsin-Madison (1991)"},{"issue":"3","key":"35_CR23","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.W.: On competitive on-line algorithms for the dynamic priority-ordering problem. Inf. Proc. Lett.\u00a051(3), 155\u2013161 (1994)","journal-title":"Inf. Proc. Lett."},{"key":"35_CR24","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: FOCS 2002, pp. 679\u2013688 (2002)","DOI":"10.1109\/SFCS.2002.1181993"},{"key":"35_CR25","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: STOC 2004, pp. 184\u2013191 (2004)","DOI":"10.1145\/1007352.1007387"},{"issue":"2","key":"35_CR26","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","volume":"13","author":"A. Sch\u00f6nhage","year":"1976","unstructured":"Sch\u00f6nhage, A., Paterson, M., Pippenger, N.: Finding the median. J. of Comput. and Syst. Sci.\u00a013(2), 184\u2013199 (1976)","journal-title":"J. of Comput. and Syst. Sci."},{"issue":"4","key":"35_CR27","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(83)90038-8","volume":"17","author":"O. Shmueli","year":"1983","unstructured":"Shmueli, O.: Dynamic cycle detection. Information Processing Letters\u00a017(4), 185\u2013188 (1983)","journal-title":"Information Processing Letters"},{"issue":"2","key":"35_CR28","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. on Comput.\u00a01(2), 146\u2013160 (1972)","journal-title":"SIAM J. on Comput."},{"issue":"3","key":"35_CR29","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.jcss.2004.04.003","volume":"69","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. of Comput. Syst. Sci.\u00a069(3), 330\u2013353 (2004)","journal-title":"J. of Comput. Syst. Sci."},{"issue":"3","key":"35_CR30","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. van Emde Boas","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett.\u00a06(3), 80\u201382 (1977)","journal-title":"Inf. Proc. Lett."},{"key":"35_CR31","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. van Emde Boas","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Mathematical Systems Theory\u00a010, 99\u2013127 (1977)","journal-title":"Mathematical Systems Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:13:15Z","timestamp":1738325595000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}