{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T02:34:00Z","timestamp":1768703640786,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,10,8]],"date-time":"2022-10-08T00:00:00Z","timestamp":1665187200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,8]],"date-time":"2022-10-08T00:00:00Z","timestamp":1665187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007642","name":"Universit\u00e0 degli Studi di Roma Tor Vergata","doi-asserted-by":"publisher","award":["E89C20000620005"],"award-info":[{"award-number":["E89C20000620005"]}],"id":[{"id":"10.13039\/501100007642","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of designing a <jats:italic>resilient<\/jats:italic> data structure maintaining a tree under the Faulty-RAM model [Finocchi and Italiano, STOC\u201904] in which up to <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b4<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> memory words can be corrupted by an adversary. Our data structure stores a rooted dynamic tree that can be updated via the addition of new leaves, requires linear size, and supports <jats:italic>resilient<\/jats:italic> (weighted) level ancestor queries, lowest common ancestor queries, and bottleneck vertex queries in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\delta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> worst-case time per operation.<\/jats:p>","DOI":"10.1007\/s00453-022-01046-3","type":"journal-article","created":{"date-parts":[[2022,10,8]],"date-time":"2022-10-08T06:03:50Z","timestamp":1665209030000},"page":"1624-1651","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees"],"prefix":"10.1007","volume":"85","author":[{"given":"Luciano","family":"Gual\u00e0","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8848-7006","authenticated-orcid":false,"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[]},{"given":"Isabella","family":"Ziccardi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,8]]},"reference":[{"key":"1046_CR1","doi-asserted-by":"crossref","unstructured":"Finocchi, I., Italiano, G.F.: Sorting and searching in the presence of memory faults (without redundancy). In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC\u201904. New York, NY, USA: Association for Computing Machinery, pp. 101\u2013110 (2004)","DOI":"10.1145\/1007352.1007375"},{"key":"1046_CR2","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Resilient search trees. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201907. USA: Society for Industrial and Applied Mathematics, pp. 547\u2013553 (2007)"},{"key":"1046_CR3","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-540-75520-3_32","volume-title":"Algorithms\u2014ESA 2007","author":"GS Brodal","year":"2007","unstructured":"Brodal, G.S., Fagerberg, R., Finocchi, I., Grandoni, F., Italiano, G.F., J\u00f8rgensen, A.G., et al.: Optimal resilient dynamic dictionaries. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) Algorithms\u2014ESA 2007, pp. 347\u2013358. Springer Berlin Heidelberg, Berlin (2007)"},{"key":"1046_CR4","first-page":"127","volume-title":"Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS\u201907). Lecture Notes in Computer Science","author":"AG J\u00f8rgensen","year":"2007","unstructured":"J\u00f8rgensen, A.G., Moruz, G., M\u00f8lhave, T.: Priority queues resilient to memory faults. In: Dehne, F.K.H.A., Sack, J., Zeh, N. (eds.) Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS\u201907). Lecture Notes in Computer Science, vol. 4619, pp. 127\u2013138. Springer, Berlin (2007)"},{"key":"1046_CR5","first-page":"13","volume-title":"Algorithms and Complexity, Proceedings of the 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Lecture Notes in Computer Science","author":"GF Italiano","year":"2010","unstructured":"Italiano, G.F.: Resilient algorithms and data structures. In: Calamoneri, T., D\u00edaz, J. (eds.) Algorithms and Complexity, Proceedings of the 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Lecture Notes in Computer Science, vol. 6078, pp. 13\u201324. Springer, Berlin (2010)"},{"key":"1046_CR6","doi-asserted-by":"publisher","first-page":"2444022","DOI":"10.1145\/2444016.2444022","volume":"8","author":"UF Petrillo","year":"2013","unstructured":"Petrillo, U.F., Grandoni, F., Italiano, G.F.: Data structures resilient to memory faults: an experimental study of dictionaries. ACM J. Exp. Algorithmics 8, 2444022 (2013). https:\/\/doi.org\/10.1145\/2444016.2444022","journal-title":"ACM J. Exp. Algorithmics"},{"key":"1046_CR7","first-page":"70:1","volume-title":"27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany. LIPIcs","author":"S Leucci","year":"2019","unstructured":"Leucci, S., Liu, C., Meierhans, S.: Resilient dictionaries for randomly unreliable memory. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany. LIPIcs, vol. 144, p. 70:1-70:16. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Wadern (2019)"},{"key":"1046_CR8","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BFb0028247","volume-title":"Algorithms and Data Structures","author":"PF Dietz","year":"1991","unstructured":"Dietz, P.F.: Finding level-ancestors in dynamic trees. In: Dehne, F., Sack, J.R., Santoro, N. (eds.) Algorithms and Data Structures, pp. 32\u201340. Springer Berlin Heidelberg, Berlin (1991)"},{"key":"1046_CR9","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP\u201900. Berlin, Heidelberg: Springer, pp. 73\u201384 (2000)","DOI":"10.1007\/3-540-45022-X_8"},{"issue":"3","key":"1046_CR10","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/s00453-012-9683-x","volume":"68","author":"ED Demaine","year":"2014","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. Algorithmica 68(3), 610\u2013625 (2014). https:\/\/doi.org\/10.1007\/s00453-012-9683-x","journal-title":"Algorithmica"},{"key":"1046_CR11","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 1014, 2000, Proceedings. Lecture Notes in Computer Science","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA Problem Revisited. In: Gonnet, G.H., Panario, D., Viola, A. (eds.) LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 1014, 2000, Proceedings. Lecture Notes in Computer Science, vol. 1776, pp. 88\u201394. Springer, Berlin (2000)"},{"issue":"4","key":"1046_CR12","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1137\/S0097539700370539","volume":"34","author":"R Cole","year":"2005","unstructured":"Cole, R., Hariharan, R.: Dynamic LCA queries on trees. SIAM J Comput. 34(4), 894\u2013923 (2005). https:\/\/doi.org\/10.1137\/S0097539700370539","journal-title":"SIAM J Comput."},{"key":"1046_CR13","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/1644015.1644016","volume":"12","author":"I Finocchi","year":"2009","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.: Resilient dictionaries. ACM Trans. Algorithms 12, 6 (2009). https:\/\/doi.org\/10.1145\/1644015.1644016","journal-title":"ACM Trans. Algorithms"},{"issue":"44","key":"1046_CR14","doi-asserted-by":"publisher","first-page":"4457","DOI":"10.1016\/j.tcs.2009.07.026","volume":"410","author":"I Finocchi","year":"2009","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Optimal resilient sorting and searching in the presence of memory faults. Theor. Comput. Sci. 410(44), 4457\u20134470 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.07.026","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1046_CR15","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J. Comput. Syst. Sci. 48(2), 214\u2013230 (1994). https:\/\/doi.org\/10.1016\/S0022-0000(05)80002-9","journal-title":"J. Comput. Syst. Sci."},{"issue":"321","key":"1046_CR16","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"01","author":"M Bender","year":"2004","unstructured":"Bender, M., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comput. Sci. 01(321), 5\u201312 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2003.05.002","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1046_CR17","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65(1), 38\u201372 (2002). https:\/\/doi.org\/10.1006\/jcss.2002.1822","journal-title":"J. Comput. Syst. Sci."},{"key":"1046_CR18","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-642-22300-6_25","volume-title":"Algorithms and Data Structures","author":"GS Brodal","year":"2011","unstructured":"Brodal, G.S., Davoodi, P., Srinivasa, Rao S.: Path minima queries in dynamic weighted trees. In: Dehne, F., Iacono, J., Sack, J.R. (eds.) Algorithms and Data Structures, pp. 290\u2013301. Springer Berlin Heidelberg, Berlin (2011)"},{"issue":"1","key":"1046_CR19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1137\/0205011","volume":"5","author":"AV Aho","year":"1976","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: On finding lowest common ancestors in trees. SIAM J. Comput. 5(1), 115\u2013132 (1976). https:\/\/doi.org\/10.1137\/0205011","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1046_CR20","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J Comput. 13(2), 338\u2013355 (1984). https:\/\/doi.org\/10.1137\/0213024","journal-title":"SIAM J Comput."},{"issue":"1\u20132","key":"1046_CR21","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0304-3975(01)00303-6","volume":"270","author":"A Pelc","year":"2002","unstructured":"Pelc, A.: Searching games with errors\u2014fifty years of coping with liars. Theor. Comput. Sci. 270(1\u20132), 71\u2013109 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00303-6","journal-title":"Theor. Comput. Sci."},{"key":"1046_CR22","first-page":"64:1","volume-title":"30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China. LIPIcs","author":"B Geissmann","year":"2019","unstructured":"Geissmann, B., Leucci, S., Liu, C., Penna, P., Proietti, G.: Dual-mode greedy algorithms can save energy. In: Lu, P., Zhang, G. (eds.) 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China. LIPIcs, vol. 149, p. 64:1-64:18. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Wadern (2019)"},{"key":"1046_CR23","first-page":"49:1","volume-title":"27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany. LIPIcs","author":"B Geissmann","year":"2019","unstructured":"Geissmann, B., Leucci, S., Liu, C., Penna, P.: Optimal Sorting with Persistent Comparison Errors. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany. LIPIcs, vol. 144, p. 49:1-49:14. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Wadern (2019)"},{"issue":"5","key":"1046_CR24","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994). https:\/\/doi.org\/10.1137\/S0097539791195877","journal-title":"SIAM J. Comput."},{"key":"1046_CR25","volume-title":"Fault-Tolerant Search Algorithms\u2014Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series","author":"F Cicalese","year":"2013","unstructured":"Cicalese, F.: Fault-Tolerant Search Algorithms\u2014Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2013)"},{"key":"1046_CR26","first-page":"1245","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19","author":"X Chen","year":"2017","unstructured":"Chen, X., Gopi, S., Mao, J., Schneider, J.: Competitive analysis of the top-K ranking problem. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 1245\u20131264. SIAM, Philadelphia (2017)"},{"key":"1046_CR27","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-030-79987-8_19","volume-title":"Combinatorial Algorithms","author":"D Dereniowski","year":"2021","unstructured":"Dereniowski, D., \u0141ukasiewicz, A., Uzna\u0144ski, P.: An Efficient Noisy Binary Search in Graphs via Median Approximation. In: Flocchini, P., Moura, L. (eds.) Combinatorial Algorithms, pp. 265\u2013281. Springer, Cham (2021)"},{"key":"1046_CR28","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-94-011-3488-0_5","volume-title":"Automated Reasoning: Essays in Honor of Woody Bledsoe. Automated Reasoning Series","author":"RS Boyer","year":"1991","unstructured":"Boyer, R.S., Moore, J.S.: MJRTY: a fast majority vote algorithm. In: Boyer, R.S. (ed.) Automated Reasoning: Essays in Honor of Woody Bledsoe. Automated Reasoning Series, pp. 105\u2013118. Kluwer, Dordrecht (1991)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01046-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01046-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01046-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T17:13:10Z","timestamp":1685121190000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01046-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,8]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1046"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01046-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,8]]},"assertion":[{"value":"19 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The study did not involve and did not use data from any of the following: human subjects, animals or biological material, plants, algae, fungi, palaeontological specimens, or geological samples.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}},{"value":"The study did not involve human subjects.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"The study did not involve human subjects.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}]}}