{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T02:38:33Z","timestamp":1725849513045},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319295152"},{"type":"electronic","value":"9783319295169"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-29516-9_13","type":"book-chapter","created":{"date-parts":[[2016,2,19]],"date-time":"2016-02-19T05:05:19Z","timestamp":1455858319000},"page":"148-160","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Subtrees Queries Revisited: The Depth First Tour Tree"],"prefix":"10.1007","author":[{"given":"Gabriele","family":"Farina","sequence":"first","affiliation":[]},{"given":"Luigi","family":"Laura","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,2,20]]},"reference":[{"key":"13_CR1","unstructured":"Acar, U.A., Blelloch, G.E., Harper, R., Vittes, J.L., Woo, S.L.M.: Dynamizing static algorithms, with applications to dynamic trees and history independence. In: SODA (2004)"},{"key":"13_CR2","unstructured":"Acar, U.A., Blelloch, G.E., Vittes, J.L: An experimental analysis of change propagation in dynamic trees. In: ALENEX (2005)"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Minimizing diameters of dynamic trees. In: ICALpP (1997)","DOI":"10.1007\/3-540-63165-8_184"},{"issue":"2","key":"13_CR4","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/1103963.1103966","volume":"1","author":"S Alstrup","year":"2005","unstructured":"Alstrup, S., Holm, J., Lichtenberg, K.D., Thorup, M.: Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1(2), 243\u2013264 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Firmani, D. and Laura, L.: Real-time analysis of critical nodes in network cores. In: IWCMC (2012)","DOI":"10.1109\/IWCMC.2012.6314175"},{"key":"13_CR6","volume-title":"Introduction to Algorithms","author":"HC Thomas","year":"2009","unstructured":"Thomas, H.C., Charles, E.L., Ronald, L.R., Clifford, S.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"13_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, 4th edn. Springer, Heidelberg (2010)","edition":"4"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"GN Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14, 781\u2013798 (1985)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"13_CR9","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/S0097539792226825","volume":"26","author":"GN Frederickson","year":"1997","unstructured":"Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26(2), 484\u2013538 (1997)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jagm.1996.0835","volume":"24","author":"GN Frederickson","year":"1997","unstructured":"Frederickson, G.N.: A data structure for dynamically maintaining rooted trees. J. Algorithms 24(1), 37\u201365 (1997)","journal-title":"J. Algorithms"},{"issue":"2","key":"13_CR11","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1921659.1921660","volume":"7","author":"L Georgiadis","year":"2011","unstructured":"Georgiadis, L., Kaplan, H., Shafrir, N., Tarjan, R.E., Werneck, R.F.: Data structures for mergeable trees. ACM Trans. Algorithms 7(2), 14 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"13_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01594940","volume":"50","author":"AV Goldberg","year":"1991","unstructured":"Goldberg, A.V., Grigoriadis, M.D., Tarjan, R.E.: Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Math. Program 50(3), 277\u2013290 (1991)","journal-title":"Math. Program"},{"issue":"4","key":"13_CR13","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"MR Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-642-30850-5_20","volume-title":"Experimental Algorithms","author":"S Joannou","year":"2012","unstructured":"Joannou, S., Raman, R.: Dynamizing succinct tree representations. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 224\u2013235. Springer, Heidelberg (2012)"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Molad, E., Tarjan, R.E.: Dynamic rectangular intersection with priorities. In: STOC (2003)","DOI":"10.1145\/780542.780635"},{"key":"13_CR16","unstructured":"Langerman, S.: On the shooter location problem. In: CCCG (2000)"},{"issue":"3","key":"13_CR17","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"13_CR18","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/297096.297144","volume":"3","author":"T Radzik","year":"1998","unstructured":"Radzik, T.: Implementation of dynamic trees with in-subtree operations. ACM J. Exp. Algorithms 3, 9 (1998)","journal-title":"ACM J. Exp. Algorithms"},{"issue":"3","key":"13_CR20","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"13_CR21","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"issue":"2","key":"13_CR22","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02614369","volume":"78","author":"RE Tarjan","year":"1997","unstructured":"Tarjan, R.E.: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program. 78(2), 169\u2013177 (1997)","journal-title":"Math. Program."},{"key":"13_CR23","unstructured":"Tarjan, R.E., Werneck, R.F.: Self-adjusting top trees. In: SODA (2005)"},{"key":"13_CR24","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1498698.1594231","volume":"14","author":"RE Tarjan","year":"2009","unstructured":"Tarjan, R.E., Werneck, R.F.: Dynamic trees in practice. ACM J. Exp. Algorithmics 14, 5 (2009)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"13_CR25","unstructured":"Werneck, R.F.: Design and analisys of data structures for dynamic trees. Ph.D thesis (2006)"},{"key":"13_CR26","volume-title":"Encyclopedia of Algorithms","author":"RF Werneck","year":"2008","unstructured":"Werneck, R.F.: Dynamic trees. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, Heidelberg (2008)"},{"issue":"1\u20136","key":"13_CR27","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF01758773","volume":"7","author":"J Westbrook","year":"1992","unstructured":"Westbrook, J., Tarjan, R.E.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7(1\u20136), 433\u2013464 (1992)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-29516-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T19:31:59Z","timestamp":1600198319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-29516-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319295152","9783319295169"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-29516-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}