The problem of computing approximate graph products was posed
several years ago in a theoretical biology context.
It leads to the problem of factorizing graphs with
respect to the strong product.
However, the information needed has to be sampled,
will always be incomplete, and have limited
accuracy. One has to work with graphs that are known only
approximately, which forces the consideration of an approximate
and local theory.
Given a graph G that is known only approximately, we
are thus given the task of finding a graph H that is a nontrivial
strong product and a 'good' approximation of G. There are many
ways to define 'good' approximations. We have to be careful to
find a definition that yields useful results and is still
computationally feasible.
To overcome this difficulty a local approach
due to Wilfried Imrich and Peter Stadler
is proposed. It leads to a local decomposition algorithm
that allows to treat this problem. It is described here, and
examples are given where it yields good results.
The diploma theses of
Aneta Macura, Michal Mrzglod, and Mateusz Olejarka
have also been written within this framework and
provide important contributions to the
factorization of graphs and the solution of
problems of this kind.