# zbMATH — the first resource for mathematics

Fast lowest common ancestor computations in dags. (English) Zbl 1151.68736
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, 705-716 (2007).
Summary: This work studies lowest common ancestor computations in directed acyclic graphs. We present fast algorithms for solving the All-Pairs Representative LCA and All-Pairs All LCA problems with expected running time of $$O(n ^{2} \log n)$$ and $$O(n ^{3} \log\log n)$$ respectively, where the expectation is taken over a distribution of input graphs. The speed-ups over recently developed methods are achieved by applying transitive reduction on the input dags. The algorithms are experimentally evaluated against previous approaches demonstrating a significant improvement. On the purely theoretical side, we improve the upper bound for All-Pairs All LCA to $$O(n ^{3.3399})$$. We give first fully dynamic algorithms for both All-Pairs Representative LCA and All-Pairs All LCA. Here, the non-trivial update complexities are $$O(n ^{2.5})$$ and $$O(n ^{3})$$ respectively, with constant query times.
For the entire collection see [Zbl 1130.68001].

##### MSC:
 68W05 Nonnumerical algorithms 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science
Full Text: