The Level-Ancestor problem on pure pointer machines

DOI10.1016/S0020-0190(02)00428-3zbMath1173.68460OpenAlexW2092431640MaRDI QIDQ1007543

Desh Ranjan, Enrico Pontelli

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00428-3

zbMATH Keywords

algorithmsdata structurestreespointer machines

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• Recognizing breadth-first search trees in linear time
• Finding level-ancestors in trees
• The nearest common ancestor in a dynamic tree
• Lower bounds for the union-find and the split-find problem on pointer machines
• Fast Algorithms for Finding Nearest Common Ancestors
• Storage Modification Machines
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching

This page was built for publication: The Level-Ancestor problem on pure pointer machines