{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:37:50Z","timestamp":1725543470867},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_8","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T01:24:10Z","timestamp":1151285050000},"page":"53-64","source":"Crossref","is-referenced-by-count":5,"title":["An ${\\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering"],"prefix":"10.1007","author":[{"given":"Deepak","family":"Ajwani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","unstructured":"Ajwani, D., Friedrich, T., Meyer, U.: An O(n\n                           2.75) algorithm for online topological ordering (2006) arXiv:cs.DS\/0602073"},{"key":"8_CR2","unstructured":"Alpern, B., Hoover, R., Rosen, B.K., Sweeney, P.F., Kenneth Zadeck, F.: Incremental evaluation of computational circuits. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 32\u201342. Society for Industrial and Applied Mathematics (1990)"},{"key":"8_CR3","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"1989","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. MIT Press, Cambridge (1989)"},{"key":"8_CR4","unstructured":"Katriel, I., Bodlaender, H.L.: Online topological ordering. In: Proceeding of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, pp. 443\u2013450 (2005)"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"8_CR6","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":"8_CR7","unstructured":"Omohundro, S.M., Lim, C., Bilmes, J.: The sather language compiler\/debugger implementation. Technical Report TR-92-017, International Computer Science Institute, Berkeley (1992)"},{"key":"8_CR8","first-page":"622","volume-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing","author":"A. \u00d6stlin","year":"2003","unstructured":"\u00d6stlin, A., Pagh, R.: Uniform hashing in constant time and linear space. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 622\u2013628. ACM Press, New York (2003)"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/978-3-540-24838-5_29","volume-title":"Experimental and Efficient Algorithms","author":"D.J. Pearce","year":"2004","unstructured":"Pearce, D.J., Kelly, P.H.J.: A dynamic algorithm for topologically sorting directed acyclic graphs. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol.\u00a03059, pp. 383\u2013398. Springer, Heidelberg (2004)"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Pearce, D.J., Kelly, P.H.J., Hankin, C.: Online cycle detection and difference propagation for pointer analysis. In: Proceedings of the Third International IEEE Workshop on Source Code Analysis and Manipulation (SCAM 2003) (2003)","DOI":"10.1109\/SCAM.2003.1238026"},{"key":"8_CR11","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. Information Processing Letters\u00a051, 155\u2013161 (1994)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:28Z","timestamp":1619493568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/11785293_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}