Models and algorithms for computing the common labelling of a set of attributed graphs

摘要

In some methodologies, it is needed a consistent common labelling between the vertices of a graph set, for instance, to compute a representative of a set of graphs. This is an NP-complete problem with an exponential computational cost depending on the number of nodes and the number of graphs. In the current paper, we present two new methodologies to compute a sub-optimal common labelling. The former focuses in extending the Graduated Assignment algorithm, although the methodology could be applied to other probabilistic graph-matching algorithms. The latter goes one step further and computes the common labelling whereby a new iterative sub-optimal algorithm. Results show that the new methodologies improve the state of the art obtaining more precise results than the most recent method with similar computational cost.