The nearest common ancestor in a dynamic tree
type: Item
instance of: scholarly article
title: The nearest common ancestor in a dynamic tree
zbMATH Open document ID: 0616.68061
DOI: 10.1007/BF00268844
author: Athanasios K. Tsakalidis
published in: Acta Informatica
publication date: 1988-01-01T00:00:00Z
review text: We consider the problem of determining the nearest common ancestor of two given nodes x and y (denoted by nca(x,y)) in a dynamic arbitrary tree T. We present an implementation of T by a pointer machine which needs linear space, performs m arbitrary insertions and deletions in the initially empty tree T in time O(m) and a query about nca(x,y) can be answered on- line in time O(log(min\(\{\) depth(x),\(depth(y)\})+\alpha (k,k))\), where the second factor is amortized over k queries, \(\alpha\) is a functional inverse of Ackermann's function and depth(x) the distance from node x to the root of T.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 3999308
zbMATH Keywords: dynamic tree
zbMATH Keywords: nearest common ancestor
zbMATH Keywords: pointer machine
MaRDI profile type: Publication
cites work: Q4091421
cites work: On Finding Lowest Common Ancestors in Trees
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: An Efficient Method for Storing Ancestor Information in Trees
cites work: A data structure for dynamic trees
cites work: A class of algorithms which require nonlinear time to maintain disjoint sets
cites work: Worst-case Analysis of Set Union Algorithms
description: scientific article; zbMATH DE number 3999308