The nearest common ancestor in a dynamic tree

DOI10.1007/BF00268844zbMath0616.68061MaRDI QIDQ1821561

Athanasios K. Tsakalidis

Publication date: 1988

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

pointer machinenearest common ancestordynamic tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (7)

Sequential and parallel algorithms for the NCA problem on pure pointer machines ⋮ Dynamic range majority data structures ⋮ Optimal pointer algorithms for finding nearest common ancestors in dynamic trees ⋮ The lowest common ancestor problem on a tree with an unfixed root ⋮ The Level-Ancestor problem on pure pointer machines ⋮ Some Results for Elementary Operations ⋮ An optimal data structure to handle dynamic environments in non-deterministic computations

Cites Work

• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• A data structure for dynamic trees
• Fast Algorithms for Finding Nearest Common Ancestors
• Worst-case Analysis of Set Union Algorithms
• An Efficient Method for Storing Ancestor Information in Trees
• On Finding Lowest Common Ancestors in Trees

This page was built for publication: The nearest common ancestor in a dynamic tree