2026-07-21T20:32:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15499 2024-03-06T10:55:27Z ddc:004 open_access

Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees Gualà, Luciano Leucci, Stefano Ziccardi, Isabella level ancestor queries lowest common ancestor queries bottleneck vertex queries resilient data structures faulty-RAM model dynamic trees We study the problem of designing a resilient data structure maintaining a tree under the Faulty-RAM model [Finocchi and Italiano, STOC'04] in which up to δ 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 resilient (weighted) level ancestor queries, lowest common ancestor queries, and bottleneck vertex queries in O(δ) worst-case time per operation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luciano Gualà and Stefano Leucci and Isabella Ziccardi 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.66 urn:nbn:de:0030-drops-154998 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.66 eng https://creativecommons.org/licenses/by/4.0/legalcode