Efficient computation of transitive closures (Q2639033)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient computation of transitive closures |
scientific article |
Statements
Efficient computation of transitive closures (English)
0 references
1990
0 references
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.
0 references
max-min composition
0 references
computational complexity
0 references
max-min closure
0 references
fuzzy proximity relation
0 references
transitive closure
0 references
space and time complexities
0 references