Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
复制标题
Dags 中独特的最低共同祖先几乎与矩阵乘法一样简单
DOI：
10.1007/978-3-540-75520-3_25
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Lingas
中科院分区：
文献类型：
--
作者：
Miroslaw Kowaluk;A. Lingas
我们考虑的问题，确定每对顶点的有向无环图（DAG）的n个顶点是否有一个唯一的最低共同祖先，如果是这样，找到这样的祖先。我们证明了这个问题可以在O（nω log n）的时间内解决，其中ω < 2.376是已知的两个n × n矩阵相乘的最快算法的指数。
我们还证明了确定n个顶点上任意dag的每对顶点的最低共同祖先的问题在时间O（n2p+nω）内可解，其中p是覆盖dag顶点的有向路的最小数目.在随机位的帮助下，我们可以在O（n2p）的时间内解决后一个问题。
We consider the problem of determining for each pair of vertices of a directed acyclic graph (dag) on n vertices whether or not it has a unique lowest common ancestor, and if so, finding such an ancestor. We show that this problem can be solved in time O(nω log n), where ω < 2.376 is the exponent of the fastest known algorithm for multiplication of two n × n matrices.
We show also that the problem of determining a lowest common ancestor for each pair of vertices of an arbitrary dag on n vertices is solvable in time O(n2p+nω), where p is the minimum number of directed paths covering the vertices of the dag. With the help of random bits, we can solve the latter problem in time O(n2p).
自动机、语言和编程
DOI：
10.1007/978-3-540-70583-3_9
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Berger M
通讯作者：
Berger M