Document Open Access Logo

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

Authors Luciano Gualà , Stefano Leucci , Isabella Ziccardi

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.66.pdf
  • Filesize: 1.01 MB
  • 17 pages

Document Identifiers

Author Details

Luciano Gualà
  • Department of Enterprise Engineering, University of Rome "Tor Vergata", Italy
Stefano Leucci
  • Department of Information Engineering, Computer Science, and Mathematics, University of L'Aquila, Italy
Isabella Ziccardi
  • Department of Information Engineering, Computer Science, and Mathematics, University of L'Aquila, Italy

Funding

  • Gualà, Luciano: This work was partially supported by the project E89C20000620005 "ALgorithmic aspects of BLOckchain TECHnology" (ALBLOTECH).

Cite AsGet BibTex

Luciano Gualà, Stefano Leucci, and Isabella Ziccardi. Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.66

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • level ancestor queries
  • lowest common ancestor queries
  • bottleneck vertex queries
  • resilient data structures
  • faulty-RAM model
  • dynamic trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. On finding lowest common ancestors in trees. SIAM J. Comput., 5(1):115-132, 1976. URL: https://doi.org/10.1137/0205011.
  2. Stephen Alstrup and Jacob Holm. Improved algorithms for finding level ancestors in dynamic trees. In Proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP '00, pages 73-84, Berlin, Heidelberg, 2000. Springer-Verlag. Google Scholar
  3. Michael Bender and Martin Farach-Colton. The level ancestor problem simplified. Theor. Comput. Sci., 321:5-12, January 2004. Google Scholar
  4. Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In Gaston H. Gonnet, Daniel Panario, and Alfredo Viola, editors, LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, volume 1776 of Lecture Notes in Computer Science, pages 88-94. Springer, 2000. URL: https://doi.org/10.1007/10719839_9.
  5. Omer Berkman and Uzi Vishkin. Finding level-ancestors in trees. J. Comput. Syst. Sci., 48(2):214-230, April 1994. URL: https://doi.org/10.1016/S0022-0000(05)80002-9.
  6. Robert S. Boyer and J. Strother Moore. MJRTY: A fast majority vote algorithm. In Robert S. Boyer, editor, Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, pages 105-118. Kluwer Academic Publishers, 1991. Google Scholar
  7. Gerth Stølting Brodal, Pooya Davoodi, and S. Srinivasa Rao. Path minima queries in dynamic weighted trees. In Frank Dehne, John Iacono, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, pages 290-301, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  8. Gerth Stølting Brodal, Rolf Fagerberg, Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano, Allan Grønlund Jørgensen, Gabriel Moruz, and Thomas Mølhave. Optimal resilient dynamic dictionaries. In Lars Arge, Michael Hoffmann, and Emo Welzl, editors, Algorithms - ESA 2007, pages 347-358, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  9. Xi Chen, Sivakanth Gopi, Jieming Mao, and Jon Schneider. Competitive analysis of the top-K ranking problem. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1245-1264. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.81.
  10. Ferdinando Cicalese. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-17327-1.
  11. Richard Cole and Ramesh Hariharan. Dynamic LCA queries on trees. SIAM J. Comput., 34(4):894-923, 2005. URL: https://doi.org/10.1137/S0097539700370539.
  12. Erik D. Demaine, Gad M. Landau, and Oren Weimann. On cartesian trees and range minimum queries. Algorithmica, 68(3):610-625, 2014. URL: https://doi.org/10.1007/s00453-012-9683-x.
  13. Dariusz Dereniowski, Aleksander Łukasiewicz, and Przemysław Uznański. An efficient noisy binary search in graphs via median approximation. In Paola Flocchini and Lucia Moura, editors, Combinatorial Algorithms, pages 265-281, Cham, 2021. Springer International Publishing. Google Scholar
  14. Paul F. Dietz. Finding level-ancestors in dynamic trees. In Frank Dehne, Jörg-Rüdiger Sack, and Nicola Santoro, editors, Algorithms and Data Structures, pages 32-40, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg. Google Scholar
  15. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM J. Comput., 23(5):1001-1018, 1994. URL: https://doi.org/10.1137/S0097539791195877.
  16. Irene Finocchi, Fabrizio Grandoni, and Giuseppe Italiano. Resilient dictionaries. ACM Transactions on Algorithms, 6, December 2009. URL: https://doi.org/10.1145/1644015.1644016.
  17. Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano. Resilient search trees. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 547-553, USA, 2007. Society for Industrial and Applied Mathematics. Google Scholar
  18. Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano. Optimal resilient sorting and searching in the presence of memory faults. Theor. Comput. Sci., 410(44):4457-4470, 2009. URL: https://doi.org/10.1016/j.tcs.2009.07.026.
  19. Irene Finocchi and Giuseppe F. Italiano. 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 '04, pages 101-110, New York, NY, USA, 2004. Association for Computing Machinery. URL: https://doi.org/10.1145/1007352.1007375.
  20. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal sorting with persistent comparison errors. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 49:1-49:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.49.
  21. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna, and Guido Proietti. Dual-mode greedy algorithms can save energy. In Pinyan Lu and Guochuan Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, volume 149 of LIPIcs, pages 64:1-64:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.64.
  22. Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338-355, 1984. URL: https://doi.org/10.1137/0213024.
  23. Giuseppe F. Italiano. Resilient algorithms and data structures. In Tiziana Calamoneri and Josep Díaz, editors, Algorithms and Complexity, 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Proceedings, volume 6078 of Lecture Notes in Computer Science, pages 13-24. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13073-1_3.
  24. Allan Grønlund Jørgensen, Gabriel Moruz, and Thomas Mølhave. Priority queues resilient to memory faults. In Frank K. H. A. Dehne, Jörg-Rüdiger Sack, and Norbert Zeh, editors, Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS'07), volume 4619 of Lecture Notes in Computer Science, pages 127-138. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-73951-7_12.
  25. Stefano Leucci, Chih-Hung Liu, and Simon Meierhans. Resilient dictionaries for randomly unreliable memory. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 70:1-70:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.70.
  26. Andrzej Pelc. Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci., 270(1-2):71-109, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00303-6.
  27. Umberto Ferraro Petrillo, Fabrizio Grandoni, and Giuseppe F. Italiano. Data structures resilient to memory faults: An experimental study of dictionaries. ACM J. Exp. Algorithmics, 18, 2013. URL: https://doi.org/10.1145/2444016.2444022.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact