Affordable Access

Publisher Website

On a relation between graph edit distance and maximum common subgraph

Authors
Journal
Pattern Recognition Letters
0167-8655
Publisher
Elsevier
Volume
18
Issue
8
Identifiers
DOI: 10.1016/s0167-8655(97)00060-3
Keywords
  • Approximate Graph Matching
  • Graph Edit Distance
  • Maximum Common Subgraph
  • Edit Operation
  • Cost Function

Abstract

Abstract In approximate, or error-correcting, graph matching one considers a set of graph edit operations, and defines the edit distance of two graphs g1 and g2 as the shortest (or least cost) sequence of edit operations that transform g1 into g2. A maximum common subgraph of two graphs g1 and g2 is a subgraph of both g1 and g2 such that there is no other subgraph of g1 and g2 with more nodes. Graph edit distance and maximum common subgraph are well known concepts that have various applications in pattern recognition and machine vision. In this paper a particular cost function for graph edit distance is introduced, and it is shown that under this cost function graph edit distance computation is equivalent to the maximum common subgraph problem.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

A graph distance metric combining maximum common s...

on Pattern Recognition Letters Jan 01, 2001

Median graph: A new exact algorithm using a distan...

on Pattern Recognition Letters Jan 01, 2009

Mean and maximum common subgraph of two graphs

on Pattern Recognition Letters Jan 01, 2000

A graph distance metric based on the maximal commo...

on Pattern Recognition Letters Jan 01, 1998
More articles like this..