• Description of LCA
• The use of LCA
• Trivial solution n^2
• Better solutions
• This Project

• Brief overview
• more info here

• Brief overview
• more info here

• Perl for Bender
• C++ for vishkin
• Library with sample drivers
• To do: mpich

We achieve O(n) preprocessing by looking at the LCA as a Range minimum problem. The Euler tour is broken into small groups, and the minimum is found of each group. Rather then calculate n^2 possibilities, we calculate the lowest ancestor over ranges that group exponentially larger. To make a query, we require 3 lookups: startblock, middle range, and endblock.

[previous slide]   [next slide]