Lowest Common Ancestor

As a lowest common ancestor ( LCA ) or 'last common ancestor " is in the computer science and graph theory refers to a determination of concept that a given rooted tree data structures efficiently preprocessed, so then queries can be answered after the last common ancestor for any node pairs in constant time .

Trees are one of the fundamental data structures in computer science. They are often used to represent data in a hierarchical or nested structure. Search and decision trees are two classic examples. Standard algorithmic questions for trees are, for example, pre-, post- and intra-traversal. A lesser known algorithmic problem in this context is the search for the last common ancestor (LCA).

Definition of the LCA

Consider a tree with a root node , a total of nodes and a height . The Lowest Common Ancestor (LCA) of two nodes and is the node that is a parent of both and and is farthest from the root , i.e. has the greatest possible depth. ${\ displaystyle T = (V, E)}$ ${\ displaystyle r}$ ${\ displaystyle n}$ ${\ displaystyle (| V | = n)}$ ${\ displaystyle h}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle r}$

The aim is to preprocess a given tree efficiently so that LCA queries can be answered as quickly as possible. ${\ displaystyle T}$ ${\ displaystyle (u, v)}$

application areas

The LCA determination can be used to determine the LCA of gene trees (bioinformatics) .

Development (history)

The LCA problem was first defined in 1973 by Alfred Aho , John Hopcroft and Jeffrey Ullman .

In 1984 Dov Harel and Robert Tarjan developed the first efficient data structure to solve the LCA problem. The input tree is preprocessed in (see Landau symbols ) so that the queries can be answered in constant time . However, the data structure is considered to be very complex and difficult to implement. Tarjan later found a simpler, albeit less efficient, algorithm that is based on the Union Find structure and that determines the LCA from a previously calculated set of node pairs (Tarjan's Offline Least Common Ancestor Algorithm (TOLCA)). In 1988, Baruch Schieber and Uzi Vishkin simplified this data structure so that it could be implemented and still required a preprocessing effort of time and a query effort . ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (1)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (1)}$

In 1993, Omer Berkman and Uzi Vishkin discovered a new way to solve the LCA problem with the help of Reduction and Range Minimum Query (RMQ) . The time required here also has a linear preprocessing time and a constant query time . This approach was simplified in 2000 by Michael Bender and Martin Farach-Colton . ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (1)}$

Web links

Determination of the lowest common ancestor using the RMQ algorithm

Individual evidence

↑ Efficient calculation of the last common ancestor and applications - FU Berlin umingo.de - accessed on March 10, 2013
↑ lowest common ancestor retrieval and other applications - University of Münster (PDF, 221 kB) uni-muenster.de - accessed on March 10, 2013
↑ Algorithms to determine the Lowest Common Ancestor (LCA) - FU Berlin (PDF, 638 kB) fu-berlin.de - accessed on March 10, 2013

[1] Efficient calculation of the last common ancestor and applications - FU Berlin umingo.de - accessed on March 10, 2013

[2] lowest common ancestor retrieval and other applications - University of Münster (PDF, 221 kB) uni-muenster.de - accessed on March 10, 2013

[3] Algorithms to determine the Lowest Common Ancestor (LCA) - FU Berlin (PDF, 638 kB) fu-berlin.de - accessed on March 10, 2013