• 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

lcalibrary is a tool that provides a way to quickly preprocess data, and a means to make LCA queries upon that data.

We currently have two methods of doing this, each implementing a specific algorithm.

Benders method - by Michael Bender and Martin Farach-Colton.

Vishkins method - by Uzi Vishkin and B. Schieber.

[previous slide]   [next slide]