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
    0 references
    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
    0 references
    0 references

    Identifiers