Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees

DOI10.1007/s00453-022-01046-3arXiv2109.09588OpenAlexW3201852533MaRDI QIDQ6103520

Luciano Gualà, Isabella Ziccardi, Stefano Leucci

Publication date: 5 June 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.09588

zbMATH Keywords

level ancestor queriesdynamic treesbottleneck vertex queriesfaulty-RAM modellowest common ancestor queriesresilient data structures

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Cartesian trees and range minimum queries
• The level ancestor problem simplified
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Optimal resilient sorting and searching in the presence of memory faults
• Finding level-ancestors in trees
• Optimal bounds for the predecessor problem and related problems
• An efficient noisy binary search in graphs via Median approximation
• Resilient dictionaries
• Fast Algorithms for Finding Nearest Common Ancestors
• Optimal Resilient Dynamic Dictionaries
• Resilient Algorithms and Data Structures
• Sorting and searching in the presence of memory faults (without redundancy)
• Priority Queues Resilient to Memory Faults
• On Finding Lowest Common Ancestors in Trees
• Computing with Noisy Information
• Competitive analysis of the top-K ranking problem
• Resilient Dictionaries for Randomly Unreliable Memory
• Data structures resilient to memory faults
• Path Minima Queries in Dynamic Weighted Trees
• Dynamic LCA Queries on Trees
• Searching games with errors -- fifty years of coping with liars