Efficient computation of transitive closures (Q2639033)

The paper provides an algorithm for calculation of transitive closure (max-min closure) of a fuzzy proximity relation (i.e., a relation that is reflexive and symmetric). The studied algorithm creates a binary tree representation of the closure in O(n log\({}_ 2n)\) time and O(n) space where ``n'' is the dimension of the relation. The algorithm is compared with a matrix method (in which its transitive closure \(R^ T\) is generated as a union of successive powers of R, say \(R^ 2,R^ 3,...)\) and Floyd's method. The performance of these methods involving different types of composition operations and properties of fuzzy relation is compared with respect to space and time complexities. A detailed numerical example is also provided.