Lowest common ancestors in trees and directed acyclic graphs

We conclude the paper with a short experimental study of LCA algorithms in trees and DAGs. Our experiments and source code demonstrate the elegance of the preprocessing-query algorithms for LCA in trees. We show that for most trees the suboptimal Θ(nlogn)-preprocessing Θ(1)-query algorithm should be preferred, and demonstrate that our proposed O(n3) algorithm for all-pairs-representative LCA in DAGs performs well in both low and high density DAGs.