What is the time taken for finding the transitive closure of a binary relation…

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. If the

original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation.

In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to

answer reachability questions. That is, can one get from node a to node other node b in one or more hops? A binary relation tells you

only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed in an

O(1) operation one may determine that node c is reachable from node a.

Warshall’s algorithm can be used to construct the Transitive closure of directed graphs (). In Warshall’s original formulation of the

algorithm, the graph is unweighted and represented by a Boolean adjacency matrix. Then the addition operation is replaced by logical

conjunction (AND) and the minimum operation by logical disjunction (OR)