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

Miroslaw Kowaluk; Andrzej Lingas

doi:10.1007/978-3-540-75520-3_25

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 › peer-review

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)$ .

Original language	English
Title of host publication	Algorithms – ESA 2007 / Lecture Notes in Computer Science
Publisher	Springer
Pages	265-274
Volume	4698
ISBN (Print)	978-3-540-75520-3
DOIs	https://doi.org/10.1007/978-3-540-75520-3_25
Publication status	Published - 2007
Event	15th Annual European Symposium on Algorithms - Eilat, Israel Duration: 2007 Oct 8 → 2007 Oct 10

Publication series

Name
Volume	4698
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th Annual European Symposium on Algorithms
Country/Territory	Israel
City	Eilat
Period	2007/10/08 → 2007/10/10

Subject classification (UKÄ)

Computer Sciences

Access to Document

10.1007/978-3-540-75520-3_25

Cite this

@inproceedings{32203b672b024c66b2d4eb17fb7d99ae,

title = "Unique lowest common ancestors in dags are almost as easy as matrix multiplication",

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\textasciicircum{}2p+n\textasciicircum{}\{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\textasciicircum{}2p)\$ .",

author = "Miroslaw Kowaluk and Andrzej Lingas",

year = "2007",

doi = "10.1007/978-3-540-75520-3\_25",

language = "English",

isbn = "978-3-540-75520-3",

volume = "4698",

publisher = "Springer",

pages = "265--274",

booktitle = "Algorithms – ESA 2007 / Lecture Notes in Computer Science",

address = "Germany",

note = "15th Annual European Symposium on Algorithms ; Conference date: 08-10-2007 Through 10-10-2007",

}

TY - GEN

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

AU - Kowaluk, Miroslaw

AU - Lingas, Andrzej

PY - 2007

Y1 - 2007

N2 - 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)$ .

AB - 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)$ .

UR - https://www.scopus.com/pages/publications/38049027404

U2 - 10.1007/978-3-540-75520-3_25

DO - 10.1007/978-3-540-75520-3_25

M3 - Paper in conference proceeding

SN - 978-3-540-75520-3

VL - 4698

SP - 265

EP - 274

BT - Algorithms – ESA 2007 / Lecture Notes in Computer Science

PB - Springer

T2 - 15th Annual European Symposium on Algorithms

Y2 - 8 October 2007 through 10 October 2007

ER -

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

Abstract

Publication series

Conference

Subject classification (UKÄ)

Access to Document

Other files and links

Fingerprint

Cite this