# 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
Full Text: