Fast Lowest Common Ancestor Computations in Dags
Fast Lowest Common Ancestor Computations in Dags
复制标题
Dags 中的快速最低共同祖先计算
DOI：
10.1007/978-3-540-75520-3_62
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Johannes Nowak
中科院分区：
文献类型：
--
作者：
Stefan Eckhardt;A. Mühling;Johannes Nowak
本文研究了有向无环图的最低共同祖先计算问题。我们提出了快速算法求解所有对代表LCA和所有对所有LCA问题的预期运行时间分别为O（n2 log n）和O（n3 log log n），其中的期望是采取了分布的输入图。最近开发的方法的速度提高是通过对输入数据应用传递约简来实现的。该算法对以前的方法进行了实验评估，表现出显着的改善。在纯理论方面，我们将ALL-PAIRS ALL LCA的上限提高到O（n3.3399）。我们首先给出了全对代表LCA和全对全LCA的全动态算法。这里，非平凡的更新复杂度分别为O（n2.5）和O（n3），查询时间不变。
This work studies lowest common ancestor computations in directed acyclic graphs. We present fast algorithms for solving the ALL-PAIRS REPRESENTATIVE LCA and ALL-PAIRS ALL LCA problems with expected running time of O(n2 log n) and O(n3 log log n) respectively, where the expectation is taken over a distribution of input graphs. The speed-ups over recently developed methods are achieved by applying transitive reduction on the input dags. The algorithms are experimentally evaluated against previous approaches demonstrating a significant improvement. On the purely theoretical side, we improve the upper bound for ALL-PAIRS ALL LCA to O(n3.3399). We give first fully dynamic algorithms for both ALL-PAIRS REPRESENTATIVE LCA and ALL-PAIRS ALL LCA. Here, the non-trivial update complexities are O(n2.5) and O(n3) respectively, with constant query times.
自动机、语言和编程
DOI：
10.1007/978-3-540-70583-3_9
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Berger M
通讯作者：
Berger M