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

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

Sammanfattning

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

Originalspråk	engelska
Titel på värdpublikation	Algorithms – ESA 2007 / Lecture Notes in Computer Science
Förlag	Springer
Sidor	265-274
Volym	4698
ISBN (tryckt)	978-3-540-75520-3
DOI	https://doi.org/10.1007/978-3-540-75520-3_25
Status	Published - 2007
Evenemang	15th Annual European Symposium on Algorithms - Eilat, Israel Varaktighet: 2007 okt. 8 → 2007 okt. 10

Publikationsserier

Namn
Volym	4698
ISSN (tryckt)	0302-9743
ISSN (elektroniskt)	1611-3349

Konferens

Konferens	15th Annual European Symposium on Algorithms
Land/Territorium	Israel
Ort	Eilat
Period	2007/10/08 → 2007/10/10

Ämnesklassifikation (UKÄ)

Datavetenskap (Datalogi)

Tillgång till dokument

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

Andra filer och länkar

Link to publication in Scopus

Citera det här

@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

Sammanfattning

Publikationsserier

Konferens

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Andra filer och länkar

Fingeravtryck

Citera det här