Improved Algorithms for the All-pairs Lowest Common Ancestor Problem in Directed Acyclic Graphs
Artur Czumaj, Andrzej Lingas · 2008
Abstract. We present a new algorithm for solving the all-pairs lowest common ancestor problem in directed acyclic graphs (dags). Our algorithm runs in time O(n 2+λ), where λ satisfies the equation ω(1,λ,1) = 1 + 2 λ and ω(1,λ,1) is the exponent of the multiplication of an n × n λ matrix by an n λ × n matrix. By the currently best bounds on ω(1, λ,1), the running time of our algorithm is O(n 2.575). Our algorithm improves upon the recent O(n 2.616)-time algorithm by Kowaluk and Lingas (ICALP’2005) and the previous O(n 2.688)-time algorithm by Bender et al. (SODA’2001). Our result is obtained by using a close relationship between the all-pairs lowest common ancestor problem in dags and the problem of computing the maximum witnesses of Boolean matrix, as well as fast Boolean multiplications of rectangular matrices. We precise the relationship by completing the proof of O(n ω)-time equivalence between the all-pairs lowest common ancestor problem and the problem of computing maximum witnesses of Boolean matrix product, where ω = ω(1,1,1) n α, the running time of our algorithm is at most O(n ω · h 0.468). This algorithm is faster than our algorithm for arbitrary dags for all values of h ≤ n 0.42. 1