Parallel transitive closure algorithm

Abstract Using the BSP/CGM model, with $$p$$ processors, where $$p \ll n$$ , we present a parallel algorithm to compute the transitive closure of a digraph $$D$$ with $$n$$ vertices and $$m$$ edges. Our algorithm uses $$\log p + 1$$ communication rounds if the input is an acyclic directed graph labe... View More