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 delta 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(delta) worst-case time per operation.
Guala', L., Leucci, S., Ziccardi, I. (2023). Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees. ALGORITHMICA, 85(6), 1624-1651 [10.1007/s00453-022-01046-3].
Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees
Guala', L;
2023-01-01
Abstract
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 delta 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(delta) worst-case time per operation.| File | Dimensione | Formato | |
|---|---|---|---|
|
algorithmica_2023_Gualà.pdf
accesso aperto
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
599.29 kB
Formato
Adobe PDF
|
599.29 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
