All-Pairs Ancestor Problems in Weighted Dags
All-Pairs Ancestor Problems in Weighted Dags
复制标题
加权 Dags 中的全对祖先问题
DOI：
10.1007/978-3-540-74450-4_26
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Johannes Nowak
中科院分区：
文献类型：
--
作者：
M. Baumgart;Stefan Eckhardt;Jan Griebsch;Sven Kosub;Johannes Nowak
本文研究了有向无环图中的（最低）公共祖先问题。通过使用快速的矩形矩阵乘法，我们改进了以前的算法为O（n2.575）的所有对代表LCA问题。我们证明了第一个非平凡的上界O（min{n2 m，n3.575}）的所有对所有最低共同祖先问题。此外，类dags确定的问题可以解决得更快。我们的算法以一对LCA的最大数量为尺度，并且-基于著名的Dilworth定理-以最大反链的大小为尺度（即，宽度）的DAG。我们扩展和推广以前的结果计算最短的祖先距离。结果表明，在加权dags中找到最短距离的共同祖先并不比计算所有对的最短距离更难，最多可达一个多对数因子。最后，我们提出了一个解决一般的所有对最短距离LCA问题的基础上计算所有对所有的LCA。
This work studies (lowest) common ancestor problems in (weighted) directed acyclic graphs. We improve previous algorithms for the all-pairs representative LCA problem to O(n2.575) by using fast rectangular matrix multiplication. We prove a first non-trivial upper bound of O(min{n2m, n3.575}) for the all-pairs all lowest common ancestors problem. Furthermore, classes of dags are identified for which the problem can be solved considerably faster. Our algorithms scale with the maximal number of LCAs for one pair and--based on the famous Dilworth's theorem--with the size of a maximum antichain (i.e., width) of the dag. We extend and generalize previous results on computing shortest ancestral distances. It is shown that finding shortest distance common ancestors in weighted dags is not harder than computing all-pairs shortest distances, up to a polylogarithmic factor. Finally, we present a solution for the general all-pairs shortest distance LCA problem based on computing all-pairs all LCAs.
自动机、语言和编程
DOI：
10.1007/978-3-540-70583-3_9
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Berger M
通讯作者：
Berger M