Computing the nearest common ancestor

This post is about computing the nearest common ancestor.  It is the result of a month or so of reading papers and implementation.  Although there has been a lot of research into the problem, there are no implementations online of the two main algorithms presented.  Worse, examples in the papers are practically useless.  For example, the Alstrup-Gavoille-Kaplan-Rauhe (AGKR) algorithm was first described in a technical report in August 2001, but it did not contain an example.  In 2002, it was presented at a conference but again it did not contain an example.  Finally, in 2004, it was published in a peer-reviewed journal and contained an example, albeit still incomplete.
Continue reading “Computing the nearest common ancestor”