We consider the problem of determining for each pair of vertices of a directed acyclic graph (dag) on n vertices whether or not it has a unique lowest common ancestor, and if so, finding such an ancestor. We show that this problem can be solved in time O(n{sup}ω log n), where ω < 2.376 is the exponent of the fastest known algorithm for multiplication of two n × n matrices. We show also that the problem of determining a lowest common ancestor for each pair of vertices of an arbitrary dag on n vertices is solvable in time O{top}~(n{sup}2p+n{sup}ω), where p is the minimum number of directed paths covering the vertices of the dag. With the help of random bits, we can solve the latter problem in time O(n{sup}2p).
展开▼
