Unique lowest common ancestors in dags are almost as easy as matrix multiplication
Författare
Summary, in English
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)$ .
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)$ .
Avdelning/ar
- Computer Science
Publiceringsår
2007
Språk
Engelska
Sidor
265-274
Publikation/Tidskrift/Serie
Algorithms – ESA 2007 / Lecture Notes in Computer Science
Volym
4698
Dokumenttyp
Konferensbidrag
Förlag
Springer
Ämne
- Computer Science
Conference name
15th Annual European Symposium on Algorithms
Conference date
2007-10-08 - 2007-10-10
Conference place
Eilat, Israel
Status
Published
Projekt
- VR 2005-4085
ISBN/ISSN/Övrigt
- ISSN: 1611-3349
- ISSN: 0302-9743
- ISBN: 978-3-540-75520-3