2020/05/22 by Torben Hagerup, Hagerup, Torben
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2005.11188
openalex publication_date 2020/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A level-ancestor or LA query about a rooted tree T takes as arguments a node v in T, of depth dv, say, and an integer d with 0≤ d≤ dv and returns the ancestor of v in T of depth d. The static LA problem is to process a given rooted tree T so as to support efficient subsequent processing of LA queries about T. All previous efficient solutions to the static LA problem work by reducing a given instance of the problem to a smaller instance of the same or a related problem, solved with a less efficient data structure, and a collection of small micro-instances for which a different solution is provided. We indicate the first efficient solution to the static LA problem that works directly, without resorting to reductions or micro-instances.