License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.66
URN: urn:nbn:de:0030-drops-154998
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15499/
Go to the corresponding LIPIcs Volume Portal

Gualà, Luciano ; Leucci, Stefano ; Ziccardi, Isabella

Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees

pdf-format:
LIPIcs-ISAAC-2021-66.pdf (1 MB)

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 δ 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.

BibTeX - Entry

@InProceedings{guala_et_al:LIPIcs.ISAAC.2021.66,
  author =	{Gual\`{a}, Luciano and Leucci, Stefano and Ziccardi, Isabella},
  title =	{{Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{66:1--66:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15499},
  URN =		{urn:nbn:de:0030-drops-154998},
  doi =		{10.4230/LIPIcs.ISAAC.2021.66},
  annote =	{Keywords: level ancestor queries, lowest common ancestor queries, bottleneck vertex queries, resilient data structures, faulty-RAM model, dynamic trees}
}

Keywords: level ancestor queries, lowest common ancestor queries, bottleneck vertex queries, resilient data structures, faulty-RAM model, dynamic trees
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI