Fast Lowest Common Ancestor Computations in Dags

This work studies lowest common ancestor problems in directed acyclic graphs. We present fast algorithms for solving the All-Pairs Representative and All-Pairs All LCA problems with expected running time of O(n^2 log n) and O(n^3 loglog n) respectively. 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 Representative LCA to O(n^2.575 ) and the upper bound for All-Pairs All LCA to O(n^3.3399 ) We give first fully dynamic algorithms for both algorithmic variants. Here, the update complexities are O(n^2.5 ) and O(n^3 ) respectively, with constant query times.     «

This work studies lowest common ancestor problems in directed acyclic graphs. We present fast algorithms for solving the All-Pairs Representative and All-Pairs All LCA problems with expected running time of O(n^2 log n) and O(n^3 loglog n) respectively. 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 theoreti...     »