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].

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