{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:33:01Z","timestamp":1794357181468,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":16,"publisher":"Springer US","isbn-type":[{"value":"9780387307701","type":"print"},{"value":"9780387301624","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_425","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:37:39Z","timestamp":1214491059000},"page":"958-961","source":"Crossref","is-referenced-by-count":1,"title":["Trade-Offs for Dynamic Graph Problems"],"prefix":"10.1007","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"425_CR1_425","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"R. Ahuja","year":"1993","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993)"},{"key":"425_CR2_425","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J.\u00a0Symb. Comput. 9, 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"425_CR3_425","volume-title":"Handbook on Data Structures and Applications (CRC Press Series, in Computer and Information Science), chap. 36","author":"C. Demetrescu","year":"2005","unstructured":"Demetrescu, C., Finocchi, I., Italiano, G.: Dynamic Graphs. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications (CRC Press Series, in Computer and Information Science), chap.\u00a036. CRC Press, Boca Raton (2005)"},{"key":"425_CR4_425","unstructured":"Demetrescu, C., Italiano, G.: Fully dynamic transitive closure: Breaking through the O(n\n                2) barrier. In: Proc. of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS'00), Redondo Beach (2000), pp. 381\u2013389"},{"key":"425_CR5_425","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1145\/1059513.1059514","volume":"52","author":"C. Demetrescu","year":"2005","unstructured":"Demetrescu, C., Italiano, G.: Trade-offs for fully dynamic reachability on dags: Breaking through the O(n\n                2) barrier. J.\u00a0ACM 52, 147\u2013156 (2005)","journal-title":"J. ACM"},{"key":"425_CR6_425","unstructured":"Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95), Milwaukee (1995), pp. 664\u2013672"},{"key":"425_CR7_425","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"X. Huang","year":"1998","unstructured":"Huang, X., Pan, V.: Fast rectangular matrix multiplication and applications. J.\u00a0Complex. 14, 257\u2013299 (1998)","journal-title":"J. Complex."},{"key":"425_CR8_425","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1002\/spe.4380111102","volume":"11","author":"D. Knuth","year":"1981","unstructured":"Knuth, D., Plass, M.: Breaking paragraphs into lines. Software-practice Exp. 11, 1119\u20131184 (1981)","journal-title":"Software-Practice Exp."},{"key":"425_CR9_425","volume-title":"Lecture Notes in Computer Science, vol. 1089","author":"G. Ramalingam","year":"1996","unstructured":"Ramalingam, G.: Bounded incremental computation. In: Lecture Notes in Computer Science, vol.\u00a01089. Springer, New York (1996)"},{"key":"425_CR10_425","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proceedings of 43th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Vancouver (2002), pp. 679\u2013688"},{"key":"425_CR11_425","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: A\u00a0fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), Chicago (2004), pp. 184\u2013191","DOI":"10.1145\/1007352.1007387"},{"key":"425_CR12_425","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: On Dynamic Shortest Paths Problems. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA), Bergen (2004), pp. 580\u2013591","DOI":"10.1007\/978-3-540-30140-0_52"},{"key":"425_CR13_425","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/FOCS.2004.25","volume-title":"FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)","author":"P. Sankowski","year":"2004","unstructured":"Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 509\u2013517. IEEE Computer Society, Washington, DC (2004)"},{"key":"425_CR14_425","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Subquadratic algorithm for dynamic shortest distances. In: 11th Annual International Conference on Computing and Combinatorics (COCOON'05), Kunming (2005), pp. 461\u2013470","DOI":"10.1007\/11533719_47"},{"key":"425_CR15_425","doi-asserted-by":"crossref","unstructured":"Schulz, F., Wagner, D., Weihe, K.: Dijkstra's algorithm on-line: an empirical case study from public railroad transport. In: Proc. 3rd Workshop on Algorithm Engineering (WAE'99), London (1999), pp. 110\u2013123","DOI":"10.1007\/3-540-48318-7_11"},{"key":"425_CR16_425","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Proc. 9-th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville (1990). pp. 230\u2013242","DOI":"10.1145\/298514.298576"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T21:56:12Z","timestamp":1662155772000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_425"}},"subtitle":["2005;\nDemetrescu, Italiano"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_425","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2008]]}}}