An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs

Computing the transitive closure of a directed graph can be reduced to determining the transitive closure of the (circuit-free) graph induced on the strongly connected components (the transitive closure of a strongly connected graph being the complete graph). A new algorithm is described to compute the transitive closure of a circuit-free graph, the complexity of which (in the worst-case sense) is better than O(MN) (M being the number of arcs and N the number of vertices). In the case of low density graphs, the resulting complexity is then better that that of previously known algorithms. In particular, for the class of low density circuitless graphs with vertices having in-degrees bounded by some fixed constant K, we show that our algorithm is linear in M′, the number of arcs in the transitive closure