Unique lowest common ancestors in dags are almost as easy as matrix multiplication
(2007) 15th Annual European Symposium on Algorithms In Algorithms – ESA 2007 / Lecture Notes in Computer Science 4698. p.265274 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)$ .
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/629395
 author
 Kowaluk, Miroslaw and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2007
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Algorithms – ESA 2007 / Lecture Notes in Computer Science
 volume
 4698
 pages
 265  274
 publisher
 Springer
 conference name
 15th Annual European Symposium on Algorithms
 external identifiers

 scopus:38049027404
 ISSN
 16113349
 03029743
 ISBN
 9783540755203
 DOI
 10.1007/9783540755203_25
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 32203b672b024c66b2d4eb17fb7d99ae (old id 629395)
 date added to LUP
 20071127 15:12:57
 date last changed
 20180304 03:35:23
@inproceedings{32203b672b024c66b2d4eb17fb7d99ae, 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.<br/><br> 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)$ .}, author = {Kowaluk, Miroslaw and Lingas, Andrzej}, booktitle = {Algorithms – ESA 2007 / Lecture Notes in Computer Science}, isbn = {9783540755203}, issn = {16113349}, language = {eng}, pages = {265274}, publisher = {Springer}, title = {Unique lowest common ancestors in dags are almost as easy as matrix multiplication}, url = {http://dx.doi.org/10.1007/9783540755203_25}, volume = {4698}, year = {2007}, }