Advanced

Unique lowest common ancestors in dags are almost as easy as matrix multiplication

Kowaluk, Miroslaw and Lingas, Andrzej LU (2007) 15th Annual European Symposium on Algorithms In Algorithms – ESA 2007 / Lecture Notes in Computer Science 4698. p.265-274
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:
author
organization
publishing date
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
0302-9743
1611-3349
ISBN
978-3-540-75520-3
DOI
10.1007/978-3-540-75520-3_25
project
VR 2005-4085
language
English
LU publication?
yes
id
32203b67-2b02-4c66-b2d4-eb17fb7d99ae (old id 629395)
date added to LUP
2007-11-27 15:12:57
date last changed
2017-04-16 03:29:50
@inproceedings{32203b67-2b02-4c66-b2d4-eb17fb7d99ae,
  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 ω&lt; 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         = {978-3-540-75520-3},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {265--274},
  publisher    = {Springer},
  title        = {Unique lowest common ancestors in dags are almost as easy as matrix multiplication},
  url          = {http://dx.doi.org/10.1007/978-3-540-75520-3_25},
  volume       = {4698},
  year         = {2007},
}