The Library
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
Tools
Czumaj, Artur, Kowaluk, Miroslaw and Lingas, Andrzej (2007) Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theoretical Computer Science, Vol.380 (No.12). pp. 3746. doi:10.1016/j.tcs.2007.02.053
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1016/j.tcs.2007.02.053
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.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Divisions:  Faculty of Science > Computer Science  
Journal or Publication Title:  Theoretical Computer Science  
Publisher:  Elsevier Science BV  
ISSN:  03043975  
Official Date:  21 June 2007  
Dates: 


Volume:  Vol.380  
Number:  No.12  
Number of Pages:  10  
Page Range:  pp. 3746  
DOI:  10.1016/j.tcs.2007.02.053  
Status:  Not Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Title of Event:  32nd International Colloquium on Automata, Languages and Programming (ICALP 2005)  
Type of Event:  Other  
Location of Event:  Lisbon, Portugal  
Date(s) of Event:  July 1115, 2005 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 