Revision #2 Authors: Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

Accepted on: 6th September 2006 00:00

Downloads: 2251

Keywords:

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

Revision #1 Authors: Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

Accepted on: 1st September 2006 00:00

Downloads: 1144

Keywords:

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

TR06-111 Authors: Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

Publication: 31st August 2006 15:50

Downloads: 2711

Keywords:

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.