ON A RELATION BETWEEN GRAPH EDIT DISTANCE AND MAXIMUM COMMON SUBGRAPH

In approximate, or error-correcting, graph matching one considers a se t of graph edit operations, and defines the edit distance of two graph s g(1) and g(2) as the shortest (or least cost) sequence of edit opera tions that transform g(1) into g(2). A maximum common subgraph of two graphs g(1) and g(2) is a subgraph of both g(1) and g(2) such that the re is no other subgraph of g(1) and g(2) with more nodes. Graph edit d istance and maximum common subgraph are well known concepts that have various applications in pattern recognition and machine vision. In thi s paper a particular cost function for graph edit distance is introduc ed, and it is shown that under this cost function graph edit distance computation is equivalent to the maximum common subgraph problem. (C) 1997 Elsevier Science B.V.