All-Pairs LCA in DAGs: Breaking through the $O(n^{2.5})$ barrier

Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz +2

Let $G=(V,E)$ be an $n$-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices $u$ and $v$ is a common ancestor $w$ of $u$ and $v$ such that no descend…