A generalization of the most common subgraph distance and its application to graph editing

作者：Hecht Michael^*

来源：Pattern Recognition Letters, 2017, 87: 71-78.

DOI：10.1016/j.patrec.2016.09.008

• Graph editing
• Most common subgraph problem
• Tree editing
• Sequence alignment
• Edit distance

We relate the graph editing distance to a generalized weighted version of the most common subgraph distance. To do so, we introduce the new concepts of isotonic shifts and vector weighted graphs. As a consequence we can give a weak but sufficient condition on cost models to result in an edit metric, ensuring the richness of the class of these functions. Moreover, for arbitrary instances we are able to determine a within cubic time computable upper bound on the edit distance, which equals the minimized distance for infinitely many instances.

• 出版日期2017-2-1