Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
and
organization
publishing date
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
2007-10-08 - 2007-10-10
external identifiers
  • scopus:38049027404
ISSN
1611-3349
0302-9743
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
2016-04-01 11:52:44
date last changed
2025-03-13 06:51:45
@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         = {{1611-3349}},
  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}},
  doi          = {{10.1007/978-3-540-75520-3_25}},
  volume       = {{4698}},
  year         = {{2007}},
}