Presentation for Open Source Project: lcalibrary
  • Description of LCA
  • The use of LCA
  • Trivial solution n^2
  • Better solutions
  • This Project
Bender's Method
  • Brief overview
  • more info here
Vishkin's Method
  • Brief overview
  • more info here
Development process
  • Perl for Bender
  • C++ for vishkin
  • Library with sample drivers
  • To do: mpich

Now that we have determined the calculation of LCA is useful, we can consider a trivial solution.

For all nodes in the tree, create a table that stores the LCA of any two nodes. So we simple calculate the LCA(X,Y) where X and Y are all the possible LCA queries based upon the tree.

This works fine, but is dreadfully slow. Supposing that our data set is huge, this would be quite tedious, in fact it is O(n^3).





[previous slide]   [next slide]


Copyright 2003, Zack Ramjan