  Fuzzy graph-based structures such as fuzzy automata, fuzzy labeled transition
systems, fuzzy Kripke models, fuzzy social networks and fuzzy interpretations
in fuzzy description logics are useful in various applications. Given two
states, two actors or two individuals $x$ and $x'$ in such structures $G$ and
$G'$, respectively, the similarity degree between them can be defined to be
$Z(x,x')$, where $Z$ is the greatest fuzzy bisimulation between $G$ and $G'$
w.r.t. some t-norm-based fuzzy logic. Such a similarity measure has the
Hennessy-Milner property of fuzzy bisimulations as a strong logical foundation.
A fuzzy bisimulation between a fuzzy structure $G$ and itself is called a fuzzy
auto-bisimulation of $G$. The greatest fuzzy auto-bisimulation of an
image-finite fuzzy graph-based structure is a fuzzy equivalence relation. It is
useful for classification and clustering.
  In this paper, we design an efficient algorithm with the complexity
$O((m\log{l} + n)\log{n})$ for computing the fuzzy partition corresponding to
the greatest fuzzy auto-bisimulation of a finite fuzzy labeled graph $G$ under
the G\"odel semantics, where $n$, $m$ and $l$ are the number of vertices, the
number of non-zero edges and the number of different fuzzy degrees of edges of
$G$, respectively. Our notion of fuzzy partition is novel, defined only for
finite sets with respect to the G\"odel t-norm, with the aim to facilitate the
computation of the greatest fuzzy auto-bisimulation. By using that algorithm,
we also provide an algorithm with the complexity $O(m\cdot\log{l}\cdot\log{n} +
n^2)$ for computing the greatest fuzzy bisimulation between two finite fuzzy
labeled graphs under the G\"odel semantics. This latter algorithm is better
(has a lower complexity order) than the previously known algorithms for the
considered problem. Our algorithms can be restated for the other mentioned
fuzzy graph-based structures.
