Graph matching by relaxation of fuzzy assignments

Abstract

Graphs are very powerful and widely used representational tools in computer applications. We present a relaxation approach to (sub)graph matching based on a fuzzy assignment matrix. The algorithm has a computational complexity of O(n/sup 2/m/sup 2/) where n and m are the number of nodes in the two graphs being matched, and can perform both exact and inexact matching. To illustrate the performance of the algorithm, we summarize the results obtained for more than 12 000 pairs of graphs of varying types (weighted graphs, attributed graphs, and noisy graphs). We also compare our results with those obtained using the graduated assignment algorithm.