ECCC-Report TR06-111https://eccc.weizmann.ac.il/report/2006/111Comments and Revisions published for TR06-111en-usWed, 06 Sep 2006 00:00:00 +0300
Revision 2
| Faster algorithms for finding lowest common ancestors in directed acyclic graphs Revision of: TR06-111 |
Artur Czumaj,
Miroslaw Kowaluk,
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2006/111#revision2We present two new methods for finding a lowest common ancestor
(LCA) for each pair of vertices of a directed acyclic graph (dag) on
$n$ vertices and $m$ edges.
The first method is surprisingly natural and solves the all-pairs
LCA problem for the input dag on $n$ vertices and $m$ edges in time
$O(nm)$.
The second method relies on a novel reduction of the all-pairs LCA
problem to the problem of finding maximum witnesses for Boolean
matrix product. We solve the latter problem and hence also the
all-pairs LCA problem in time $O(n^{2+\lambda})$, where $\lambda $
satisfies the equation $\omega(1, \lambda, 1) = 1 + 2 \, \lambda $
and $\omega(1, \lambda, 1)$ is the exponent of the multiplication of
an $n \times n^{\lambda}$ matrix by an $n^{\lambda} \times n$
matrix. By the currently best bounds on $\omega(1,\lambda,1)$, the
running time of our algorithm is $O(n^{2.575})$. Our algorithm
improves
the previously known $O(n^{2.688})$ time-bound for the general
all-pairs LCA problem in dags by Bender \emph{et al.}
Our additional contribution is a faster algorithm for solving the
all-pairs lowest common ancestor problem in dags of small depth,
where the depth of a dag is defined as the length of the longest
path in the dag. For all dags of depth at most $h \le n^{\alpha}$,
where $\alpha \approx 0.294$, our algorithm runs in time
asymptotically the same as that of multiplying two $n \times n$
matrices, that is, $O(n^{\omega})$; we also prove that this running
time is optimal even for dags of depth $1$. For dags with depth $h
> n^{\alpha}$, the running time of our algorithm is at most
$O(n^{\omega} \cdot h^{0.468})$. This algorithm is faster than our
algorithm for arbitrary dags for all values of $h \le n^{0.42}$.
Wed, 06 Sep 2006 00:00:00 +0300https://eccc.weizmann.ac.il/report/2006/111#revision2
Revision 1
| Faster algorithms for finding lowest common ancestors in directed acyclic graphs Revision of: TR06-111 |
Artur Czumaj,
Miroslaw Kowaluk,
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2006/111#revision1We present two new methods for finding a lowest common ancestor
(LCA) for each pair of vertices of a directed acyclic graph (dag) on
$n$ vertices and $m$ edges.
The first method is surprisingly natural and solves the all-pairs
LCA problem for the input dag on $n$ vertices and $m$ edges in time
$O(nm)$.
The second method relies on a novel reduction of the all-pairs LCA
problem to the problem of finding maximum witnesses for Boolean
matrix product. We solve the latter problem and hence also the
all-pairs LCA problem in time $O(n^{2+\lambda})$, where $\lambda $
satisfies the equation $\omega(1, \lambda, 1) = 1 + 2 \, \lambda $
and $\omega(1, \lambda, 1)$ is the exponent of the multiplication of
an $n \times n^{\lambda}$ matrix by an $n^{\lambda} \times n$
matrix. By the currently best bounds on $\omega(1,\lambda,1)$, the
running time of our algorithm is $O(n^{2.575})$. Our algorithm
improves
the previously known $O(n^{2.688})$ time-bound for the general
all-pairs LCA problem in dags by Bender \emph{et al.}
Our additional contribution is a faster algorithm for solving the
all-pairs lowest common ancestor problem in dags of small depth,
where the depth of a dag is defined as the length of the longest
path in the dag. For all dags of depth at most $h \le n^{\alpha}$,
where $\alpha \approx 0.294$, our algorithm runs in time
asymptotically the same as that of multiplying two $n \times n$
matrices, that is, $O(n^{\omega})$; we also prove that this running
time is optimal even for dags of depth $1$. For dags with depth $h
> n^{\alpha}$, the running time of our algorithm is at most
$O(n^{\omega} \cdot h^{0.468})$. This algorithm is faster than our
algorithm for arbitrary dags for all values of $h \le n^{0.42}$.
Fri, 01 Sep 2006 00:00:00 +0300https://eccc.weizmann.ac.il/report/2006/111#revision1
Paper TR06-111
| Faster algorithms for finding lowest common ancestors in directed acyclic graphs |
Artur Czumaj,
Miroslaw Kowaluk,
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2006/111We present two new methods for finding a lowest common ancestor (LCA)
for each pair of vertices of a directed acyclic graph (dag) on
n vertices and m edges.
The first method is a natural approach that solves the all-pairs LCA
problem for the input dag in time O(nm).
The second method relies on a novel reduction of the all-pairs LCA
problem to the problem of finding maximum witnesses for Boolean
matrix product. We solve the latter problem and hence also the all-pairs
LCA problem in time O(n^{2.575}).
Our additional contribution is a faster algorithm for solving the all-pairs LCA problem in graphs of small depth.
Thu, 31 Aug 2006 15:50:37 +0300https://eccc.weizmann.ac.il/report/2006/111