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 t hat 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 edi t operations that transform g into g'. It will be shown that under a partic ular set of cost functions for any two graphs, g and g', a maximum common s ubgraph is a mean. Moreover, any subgraph of g or g' that contains a maximu m common subgraph is a mean as well. (C) 2000 Elsevier Science B.V. All rig hts reserved.