{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:43:48Z","timestamp":1792111428054,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":10,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_158","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:51:54Z","timestamp":1553097114000},"page":"808-809","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fully Dynamic Transitive Closure"],"prefix":"10.1007","author":[{"given":"Valerie","family":"King","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"2","key":"158_CR6378","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1145\/1059513.1059514","volume":"52","author":"C Demestrescu","year":"2005","unstructured":"Demestrescu C, Italiano GF (2005) Trade-offs for fully dynamic transitive closure on DAG's: breaking through the O(n2) barrier, (presented in FOCS 2000). J ACM 52(2):147\u2013156","journal-title":"J ACM"},{"issue":"6","key":"158_CR6379","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C Demestrescu","year":"2004","unstructured":"Demestrescu C, Italiano GF (2004) A new approach to dynamic all pairs shortest paths, (presented in STOC 2003). J ACM 51(6):968\u2013992","journal-title":"J ACM"},{"key":"158_CR6380","doi-asserted-by":"crossref","unstructured":"Frigioni D, Miller T, Nanni U, Zaroliagis CD (2001) An experimental study of dynamic algorithms for transitive closure. ACM J Exp Algorithms 6(9)","DOI":"10.1145\/945394.945403"},{"key":"158_CR6381","doi-asserted-by":"crossref","unstructured":"King V (1999) Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proceedings of the 40th annual IEEE symposium on foundation of computer science (ComiIEEE FOCS). IEEE Computer Society, New York, pp 81\u201391","DOI":"10.1109\/SFFCS.1999.814580"},{"issue":"1","key":"158_CR6382","first-page":"150","volume":"65","author":"V King","year":"2002","unstructured":"King V, Sagert G (2002) A fully dynamic algorithm for maintaining the transitive closure (presented in FOCS 1999). JCCS 65(1):150\u2013167","journal-title":"JCCS"},{"key":"158_CR6383","doi-asserted-by":"crossref","unstructured":"King V, Thorup M (2001) A space saving trick for dynamic transitive closure and shortest path algorithms. In: Proceedings of the 7th annual international conference of computing and cominatorics (COCOON). Lecture notes computer science, vol 2108\/2001. Springer, Heidelberg, pp\u00a0269\u2013277","DOI":"10.1007\/3-540-44679-6_30"},{"key":"158_CR6384","unstructured":"Roditty L (2003) A faster and simpler fully dynamic transitive closure. In: Proceedings of the 14th annual ACM-SIAM symposium on discrete algorithms (ACMIEEE SODA). ACM, Baltimore, pp 404\u2013412"},{"key":"158_CR6385","doi-asserted-by":"crossref","unstructured":"Roditty L, Zwick U (2002) Improved dynamic reachability algorithms for directed graphs. In: Proceedings of the 43rd annual symposium on foundation of computer science (IEEE FOCS). IEEE Computer Society, Vancouver, pp 679\u2013688","DOI":"10.1109\/SFCS.2002.1181993"},{"key":"158_CR6386","doi-asserted-by":"crossref","unstructured":"Roditty L, Zwick U (2004) A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proceedings of the 36th ACM symposium on theory of computing (ACMSTOC). ACM, Chicago, pp 184\u2013191","DOI":"10.1145\/1007352.1007387"},{"key":"158_CR6387","doi-asserted-by":"crossref","unstructured":"Sankowski S (2004) Dynamic transitive closure via dynamic matrix inverse. In: Proceedings of the 45th annual symposium on foundations of computer science (IEEE FOCS). IEEE Computer Society, Rome, pp 509\u2013517","DOI":"10.1109\/FOCS.2004.25"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:44:51Z","timestamp":1792107891000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_158","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}