What are the practical applications of the lowest common ancestor algorithms?

Question

I was having a look at this question and then reading about Tarjan's least common ancestors algorithm. I never came across any applications of LCA algorithms before.

Where are such LCA algorithms commonly used?

Answer 1

Don't know where it is used, but I have a couple ideas where it might get used:

• computer graphics: often 3D sceneries get split into cubes which form a tree structure. If you have an object which is contained in two such cubes a LCA algorithm gives you the smallest containing larger cube.

• analysis of gens in order to find the relationships between species and their lowest common ancestor

• merge algorithms of version control systems

Answer 2

In compilers, the LCA of two basic blocks is a place you can put a computation so it is available to both. This might be useful for eliminating common subexpressions, or inserting phi-node for SSA conversion. These algorithms are well evolved and highly optimized, though, so the LCA itself may be hard to see, e.g., SSA and PRE

Answer 3

I just wrote a blog post about how I had to implement my own algorithm for this problem (extended to a set of nodes with an arbitrary length) for a taxonomy tree in the context of metagenomics:

http://blog.bio4j.com/2012/02/finding-the-lowest-common-ancestor-of-a-set-of-ncbi-taxonomy-nodes-with-bio4j/

Cheers,

Pablo