# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### Faster algorithms for finding lowest common ancestors in directed acyclic graphs

and Lingas, Andrzej LU (2007) In Theoretical Computer Science 380(1-2). p.37-46
Abstract
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 0 (n m). 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 0 (n (2+lambda)), where A satisfies the equation to (1, lambda, I) = 1 + 2 lambda and w (1, lambda, 1) is the exponent of the multiplication of an n x n (lambda) matrix by an n (lambda) x n matrix. By the currently best known... (More)
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 0 (n m). 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 0 (n (2+lambda)), where A satisfies the equation to (1, lambda, I) = 1 + 2 lambda and w (1, lambda, 1) is the exponent of the multiplication of an n x n (lambda) matrix by an n (lambda) x n matrix. By the currently best known bounds on w 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 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 <= n alpha where alpha approximate to 0.294, our algorithm runs in a time that is asymptotically the same as that required for multiplying two n x n matrices, that is, O (n (w)); 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 (w) ho (0.468)). This algorithm is faster than our algorithm for arbitrary dags for all values of h <= n (0.42). (C) 2007 Elsevier B. V. All rights reserved. (Less)
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
directed acyclic graphs, lowest common ancestors, matrix, multiplication, time complexity
in
Theoretical Computer Science
volume
380
issue
1-2
pages
37 - 46
publisher
Elsevier
external identifiers
• wos:000247766100004
• scopus:34248548511
ISSN
0304-3975
DOI
10.1016/j.tcs.2007.02.053
project
VR 2005-4085
language
English
LU publication?
yes
id
22a5680f-0c45-4572-8686-b3b4438faab5 (old id 693067)
2016-04-01 16:54:30
date last changed
2020-01-16 01:46:30
```@article{22a5680f-0c45-4572-8686-b3b4438faab5,
abstract     = {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 0 (n m). 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 0 (n (2+lambda)), where A satisfies the equation to (1, lambda, I) = 1 + 2 lambda and w (1, lambda, 1) is the exponent of the multiplication of an n x n (lambda) matrix by an n (lambda) x n matrix. By the currently best known bounds on w 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 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 &lt;= n alpha where alpha approximate to 0.294, our algorithm runs in a time that is asymptotically the same as that required for multiplying two n x n matrices, that is, O (n (w)); we also prove that this running time is optimal even for dags of depth 1. For dags with depth h &gt; n (alpha) the running time of our algorithm is at most O (n (w) ho (0.468)). This algorithm is faster than our algorithm for arbitrary dags for all values of h &lt;= n (0.42). (C) 2007 Elsevier B. V. All rights reserved.},
author       = {Czumaj, Artur and Kowaluk, Miroslaw and Lingas, Andrzej},
issn         = {0304-3975},
language     = {eng},
number       = {1-2},
pages        = {37--46},
publisher    = {Elsevier},
series       = {Theoretical Computer Science},
title        = {Faster algorithms for finding lowest common ancestors in directed acyclic graphs},
url          = {http://dx.doi.org/10.1016/j.tcs.2007.02.053},
doi          = {10.1016/j.tcs.2007.02.053},
volume       = {380},
year         = {2007},
}

```