We 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}.

We 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}.

We 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.