Least Common Ancestors in Trees and Directed Acyclic Graphs Export

@misc{citeulike:4633, abstract = {and with a nave algorithm. We compare the performance of these algorithms as a function of the number of queries performed and the imbalance of the tree. For DAGs, we compare a transitive-closure based algorithm, an intelligent traversal algorithm, and our input-sensitive algorithm that uses LCA in trees. We compare the performance of these algorithms as a function of DAG density. We show that the input-sensitive algorithm outperforms the other two algorithms on all test data. Keywords:...}, author = {Bender, Michael A. and Farach-Colton, Martin and Pemmasani, Giridhar and Skiena, Steven and Sumazin, Pavel}, citeulike-article-id = {4633}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.1491}, keywords = {algorithms, data-structures, least-common-ancestor}, posted-at = {2004-12-23 02:21:14}, title = {Least Common Ancestors in Trees and Directed Acyclic Graphs}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.1491} }

TY - GEN ID - citeulike:4633 L3 - citeulike-article-id:4633 N2 - and with a nave algorithm. We compare the performance of these algorithms as a function of the number of queries performed and the imbalance of the tree. For DAGs, we compare a transitive-closure based algorithm, an intelligent traversal algorithm, and our input-sensitive algorithm that uses LCA in trees. We compare the performance of these algorithms as a function of DAG density. We show that the input-sensitive algorithm outperforms the other two algorithms on all test data. Keywords:... TI - Least Common Ancestors in Trees and Directed Acyclic Graphs KW - algorithms KW - data-structures KW - least-common-ancestor AU - Bender, Michael AU - Farach-Colton, Martin AU - Pemmasani, Giridhar AU - Skiena, Steven AU - Sumazin, Pavel UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.1491 ER -