A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
复制标题
DOI：
10.1016/j.tcs.2013.09.030
复制
发表时间：
2013-11-18
影响因子：
1.1
通讯作者：
Christianson, Bruce
中科院分区：
文献类型：
--
作者：
Dash, Santanu Kumar;Scholz, Sven-Bodo;Christianson, Bruce
经过线性时间预处理后，树中顶点对的LCA计算可以在常数时间内完成。然而，由于DAG中的非树边，将这些技术扩展到计算DAG中顶点对的LCA是不可能的。本文提出了一种计算DAG中顶点对LCA的算法，该算法将DAG的生成树及其非树边分开处理。我们的方法使我们能够利用现有的树木LCA算法的效率。此外，我们的算法将DAG分解为一组称为簇的组件树，这大大减少了在LCA计算中合并非树边所需的预处理。根据DAG中非树边的发生率，我们的算法无缝地在树的最佳算法和DAG的最佳算法之间插入性能图。使用所提出的技术，可以实现稀疏dag的近线性预处理和恒定的查询时间。(C) 2013 Elsevier B.V.版权所有
LCA computation for vertex pairs in trees can be achieved in constant time after linear-time preprocessing. However, extension of these techniques to compute LCA for vertex-pairs in DAGs has been not possible due to the non-tree edges in a DAG. In this paper, we present an algorithm for computing the LCA for vertex pairs in a DAG which treats the DAG's spanning tree and its non-tree edges separately. Our approach enables us to tap the efficiency of existing LCA algorithms for trees. Furthermore, our algorithm decomposes the DAG into a set of component trees called clusters which significantly reduces the preprocessing necessary to incorporate non-tree edges in the LCA computation. Our algorithm seamlessly interpolates the performance graph between the best reported algorithms for trees and the best reported algorithms for DAGs depending on the incidence of non-tree edges in the DAG. Using the proposed techniques, it is possible to achieve near-linear preprocessing and constant query time for sparse DAGs. (C) 2013 Elsevier B.V. All rights reserved.