ProV Logo
0
Static Level Ancestors in Practice
Mabrey, Matthew...

Free

Static Level Ancestors in Practice by Mabrey, Matthew ( Author )
Lemonjar Open Access
Australian National University
04-08-2023
Given a rooted tree T, the level ancestor problem aims to answer queries of the form LA(v, d), which identify the level d ancestor of a node v in the tree. Several algorithms of varied complexity have been proposed for this problem in the literature, including optimal solutions that preprocess the tree $T$ in linear bounded time and proceed to answer queries in constant time. Despite its significance and numerous applications, to date there have been no comparative studies of the performance of these algorithms and few implementations are widely available. In our experimental study we implemented and compared several solutions to the level ancestor problem, including three theoretically optimal algorithms, and examined their space requirements and time performance in practice.
-
Article
pdf
29.34 KB
English
-
MYR 0.01
-
http://arxiv.org/abs/1402.2741
Share this eBook