TWO ALGORITHMS FOR FAST INCREMENTAL TRANSITIVE CLOSURE OF SPARSE FUZZY BINARY RELATIONS

摘要

Sparse fuzzy ordering and partial ordering relations have recently become of great importance in the field of knowledge systems. As the size of the relations utilized in such a framework is extremely large, efficient algorithms are needed for their handling. More specifically, when a part of such a relation is updated, the property of transitivity needs to be re-established in timely manner, as the knowledge system often becomes unusable until this process is completed. In this paper we propose two algorithms for the incremental update of fuzzy transitive relations. The first one focuses on the incremental update of a part of an already transitive relation, while the other tackles the complete transitive closure of any relation. For the average sparse relation, both of the proposed algorithms have considerably smaller computational complexity than the classical approach, which we also prove experimentally via application to real life relations of this type.