Advanced

Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Czumaj, Artur; Kowaluk, Miroslaw 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)
Please use this url to cite or link to this publication:
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)
date added to LUP
2007-12-06 11:45:23
date last changed
2017-08-20 04:31:20
@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},
  keyword      = {directed acyclic graphs,lowest common ancestors,matrix,multiplication,time complexity},
  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},
  volume       = {380},
  year         = {2007},
}