Mixed-approach algorithms for transitive closure (extended abstract)
Håkan Jakobsson · 1991
We study two different approaches for computing the transitive closure of a directed graph and show that, in some sense, they are "dual" on edge-reversed graphs but, nevertheless, can differ asymptotically in cost on the same family of graphs.We show how the two approaches can be mixed into a new algorithm using reachability trees.We show that the new algorithm is o(~(~,yj~vxv CON~(Z, y)) where COMV(z, y) is the pairwise connectivity of z and y, and give a more exact connectivity-based upper bound that is better than the lower bound for a wide class of other algorithms on every family of graphs.