Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9656999 | Journal of Algorithms | 2005 | 20 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael A. Bender, MartÃn Farach-Colton, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin,