Unique lowest common ancestors in dags are almost as easy as matrix multiplication
(2007) 15th Annual European Symposium on Algorithms 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:
https://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
 host publication
 Algorithms – ESA 2007 / Lecture Notes in Computer Science
 volume
 4698
 pages
 265  274
 publisher
 Springer
 conference name
 15th Annual European Symposium on Algorithms
 conference location
 Eilat, Israel
 conference dates
 20071008  20071010
 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
 20160401 11:52:44
 date last changed
 20210601 04:00:16
@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}, doi = {10.1007/9783540755203_25}, volume = {4698}, year = {2007}, }