zbMATH — the first resource for mathematics

Fast algorithms for finding nearest common ancestors. (English) Zbl 0535.68022
The following problem is considered: Given a collection of rooted trees, answer queries of the form: ”What is the nearest common ancestor of vertices x and y?” The problem has different versions and different machine models can be used for its solution. The authors consider five versions of the problem and compare their solutions with two types of machines: pointer machines and random-access machines. They show that there are differences in power between pointer machines and random-access machines (the latter ones are more powerful) for some versions ot the problem.
Reviewer: M.Kratko

68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68R10 Graph theory (including graph drawing) in computer science
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
Full Text: DOI