Mean and maximum common subgraph of two graphs

摘要

A mean of a pair of graphs, g_1 and g_2, is formally defined as a graph that minimizes the sum of edit distances to g_1 and g_2. 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.