Unique lowest common ancestors in dags are almost as easy as matrix multiplication
Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
Abstract
We consider the problem of determining for each pair of vertices of a directed acyclic graph (dag) on n vertices whether or not it has a unique lowest common ancestor, and if so, finding such an ancestor. We show that this problem can be solved in time O(n ω logn), where ω< 2.376 is the exponent of the fastest known algorithm for multiplication of two n×n matrices.
We show also that the problem of determining a lowest common ancestor for each pair of vertices of an arbitrary dag on n vertices is solvable in time $widetilde{O}(n^2p+n^{omega})$ , where p is the minimum number of directed paths covering the vertices of the dag. With the help of random bits, we can solve the latter problem in time $widetilde{O}(n^2p)$ .
We show also that the problem of determining a lowest common ancestor for each pair of vertices of an arbitrary dag on n vertices is solvable in time $widetilde{O}(n^2p+n^{omega})$ , where p is the minimum number of directed paths covering the vertices of the dag. With the help of random bits, we can solve the latter problem in time $widetilde{O}(n^2p)$ .
Details
Authors  

Research areas and keywords  Subject classification (UKÄ) – MANDATORY

Original language  English 

Title of host publication  Algorithms – ESA 2007 / Lecture Notes in Computer Science 
Publisher  Springer 
Pages  265274 
Volume  4698 
ISBN (Print)  9783540755203 
Publication status  Published  2007 
Publication category  Research 
Peerreviewed  Yes 
Event  15th Annual European Symposium on Algorithms  Eilat, Israel Duration: 2007 Oct 8 → 2007 Oct 10 
Publication series
Name  

Volume  4698 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  15th Annual European Symposium on Algorithms 

Country  Israel 
City  Eilat 
Period  2007/10/08 → 2007/10/10 