Transitive Closure - Algorithms

Algorithms

Efficient algorithms for computing the transitive closure of a graph can be found in Nuutila (1995). The simplest technique is probably the Floyd–Warshall algorithm. The fastest worst-case methods, which are not practical, reduce the problem to matrix multiplication.

More recent research went into efficient ways of computing transitive closure on distributed systems based on the MapReduce paradigm (Afrati et al. 2011).