Faster algorithms for finding lowest common ancestors in directed acyclic graphs
(2007) In Theoretical Computer Science 380(12). p.3746 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 allpairs 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 allpairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem (and hence also the allpairs 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 allpairs 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 allpairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem (and hence also the allpairs 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)) timebound for the general allpairs LCA problem in dags by Bender et al. Our additional contribution is a faster algorithm for solving the allpairs 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:
http://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
 12
 pages
 37  46
 publisher
 Elsevier
 external identifiers

 wos:000247766100004
 scopus:34248548511
 ISSN
 03043975
 DOI
 10.1016/j.tcs.2007.02.053
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 22a5680f0c4545728686b3b4438faab5 (old id 693067)
 date added to LUP
 20071206 11:45:23
 date last changed
 20170820 04:31:20
@article{22a5680f0c4545728686b3b4438faab5, 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 allpairs 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 allpairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem (and hence also the allpairs 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)) timebound for the general allpairs LCA problem in dags by Bender et al. Our additional contribution is a faster algorithm for solving the allpairs 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 = {03043975}, keyword = {directed acyclic graphs,lowest common ancestors,matrix,multiplication,time complexity}, language = {eng}, number = {12}, pages = {3746}, 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}, }