Faster algorithms for finding lowest common ancestors in directed acyclic graphs
(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:
https://lup.lub.lu.se/record/693067
- author
- Czumaj, Artur ; Kowaluk, Miroslaw and Lingas, Andrzej LU
- organization
- publishing date
- 2007
- 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
- 2016-04-01 16:54:30
- date last changed
- 2022-03-22 22:02:27
@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 <= 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.}},
author = {{Czumaj, Artur and Kowaluk, Miroslaw and Lingas, Andrzej}},
issn = {{0304-3975}},
keywords = {{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}},
doi = {{10.1016/j.tcs.2007.02.053}},
volume = {{380}},
year = {{2007}},
}