The level ancestor problem simplified. (English) Zbl 1068.68047
Summary: We present a simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(\(v,d\)) requests the depth \(d\) ancestor of node \(v\). The Level Ancestor Problem is to preprocess a given rooted tree \(T\) to support level ancestor queries. While optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.
References:
| [1] | S. Alstrup, J. Holm, Improved algorithms for finding level-ancestors in dynamic trees, in: 27th Internat. Colloquium on Automata, Languages and Programming (ICALP), Geneva, Switzerland, Lecture Notes in Comput. Sci. Vol. 1853, Springer, Berlin, 2000, pp. 73-84.; S. Alstrup, J. Holm, Improved algorithms for finding level-ancestors in dynamic trees, in: 27th Internat. Colloquium on Automata, Languages and Programming (ICALP), Geneva, Switzerland, Lecture Notes in Comput. Sci. Vol. 1853, Springer, Berlin, 2000, pp. 73-84. · Zbl 0973.68665 |
| [2] | M.A. Bender, E. Demaine, M. Farach-Colton, Cache-oblivious B-trees, in: 41st Annual Symp. on Foundations of Computer Science (FOCS), 2000, pp. 399-409.; M.A. Bender, E. Demaine, M. Farach-Colton, Cache-oblivious B-trees, in: 41st Annual Symp. on Foundations of Computer Science (FOCS), 2000, pp. 399-409. |
| [3] | Berkman, O.; Vishkin, U., Finding level-ancestors in trees, J. Comput. System Sci., 48, 2, 214-230 (1994) · Zbl 0806.68027 |
| [4] | P.F. Dietz, Finding level-ancestors in dynamic trees, in: Workshop on Algorithms and Data Structures (WADS), Ottawa, Canada, 1991, pp. 32-40.; P.F. Dietz, Finding level-ancestors in dynamic trees, in: Workshop on Algorithms and Data Structures (WADS), Ottawa, Canada, 1991, pp. 32-40. · Zbl 0765.68025 |
| [5] | Gabow, H. N.; Tarjan, R. E., A linear-time algorithm for a special case of disjoint set union, J. Comput. System Sci., 30, 2, 209-221 (1985) · Zbl 0572.68058 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
