Computing markings for fuzzy minimax nets over the Gödel structure
Data Structures and Algorithms
Summary
The authors focus on fuzzy minimax nets, a tool used to compare two fuzzy graph-like structures by finding the best match between them. They created a faster method to find the biggest correct way to mark nodes in these fuzzy nets when using the Gödel structure, and this method runs quickly in relation to the net's size. Using this approach, they also developed the first algorithm to efficiently find the greatest fuzzy directed simulation between two fuzzy graphs over the Gödel structure, with a time complexity based on the number of nodes and edges. This makes comparing fuzzy graphs much more practical for larger examples.
Authors
Linh Anh Nguyen
Abstract
Fuzzy minimax nets were recently introduced as a tool for computing the greatest fuzzy bisimulation and simulation between two finite fuzzy graph-based structures. In this work, we provide an efficient algorithm for computing the greatest correct marking of a finite fuzzy minimax net over the Gödel structure. Its time complexity is linear in the number of nodes and positive edges in the input net. Building on this result, we derive the first algorithm with time complexity $O((m+n)n)$ for computing the greatest fuzzy directed simulation between two finite fuzzy graphs over the Gödel structure, where $n$ and $m$ denote the total numbers of vertices and positive edges, respectively, in the input graphs.