On the Computation of the Common Labelling of a Set of Attributed Graphs

摘要

In some methodologies, it is needed a consistent common labelling between the vertices of a set of graphs, for instance, to compute a representative of a set of graphs. This is a NP-problem with an exponential computational cost depending on the number of nodes and the number of graphs. The aim of this paper is twofold. On one hand, we aim to establish a technical methodology to define this problem for the present and further research. On the other hand, we present two sub-optimal algorithms to compute the labelling between a set of graphs. Results show that our new algorithms are able to find a consistent common labelling while reducing, most of the times, the mean distance of the AG set.