×

zbMATH — the first resource for mathematics

Unique lowest common ancestors in dags are almost as easy as matrix multiplication. (English) Zbl 1151.68429
Arge, Lars (ed.) et al., Algorithms – ESA 2007. 15th annual European symposium, Eilat, Israel, October 8–10, 2007, Proceedings. Berlin: Springer (ISBN 978-3-540-75519-7/pbk). Lecture Notes in Computer Science 4698, 265-274 (2007).
Summary: 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 ^{\omega } \log n)\), where \(\omega < 2.376\) is the exponent of the fastest known algorithm for multiplication of two \(n\times 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 the notation \(\widetilde{O}(f(n))\) stands for \(O(f(n)\log^c n)\) for some positive constant \(c\)), 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)\).
For the entire collection see [Zbl 1130.68001].

MSC:
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI