Mean and maximum common subgraph of two graphs
A mean of a pair of graphs, g1 and g2, is formally defined as a graph that minimizes the sum of edit distances to g1 and g2. The edit distance of two graphs g and g? is the minimum cost taken over all sequences of edit operations that transform g into g?. It will be shown that under a particular set of cost functions for any two graphs, g and g?, a maximum common subgraph is a mean. Moreover, any subgraph of g or g? that contains a maximum common subgraph is a mean as well.
maximum common subgraph edit distance graph matching median graph clustering