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

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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

Detaljer

Författare
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikationAlgorithms – ESA 2007 / Lecture Notes in Computer Science
FörlagSpringer
Sidor265-274
Volym4698
ISBN (tryckt)978-3-540-75520-3
StatusPublished - 2007
PublikationskategoriForskning
Peer review utfördJa
Evenemang15th Annual European Symposium on Algorithms - Eilat, Israel
Varaktighet: 2007 okt 82007 okt 10

Publikationsserier

Namn
Volym4698
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

Konferens15th Annual European Symposium on Algorithms
LandIsrael
OrtEilat
Period2007/10/082007/10/10