Graph matching is the problem of finding a similarity between

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

s.Endika Bengoetxea
"Inexact Graph Matching Using Estimation of Distribution Algorithms"
Ph. D., 2002
Chapter 2:The graph matching problem
(retrieved June 28, 2017) Graphs are commonly used to encode structural information in many fields, including

computer vision Computer vision is an Interdisciplinarity, interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate t ...

and

pattern recognition Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphic ...

, and graph matching is an important tool in these areas. Endika Bengoetxea, Ph.D.
Abstract
/ref> In these areas it is commonly assumed that the comparison is between the ''data graph'' and the ''model graph''. The case of exact graph matching is known as the

graph isomorphism problem The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational comp ...

. The problem of exact matching of a graph to a part of another graph is called subgraph isomorphism problem. Inexact graph matching refers to matching problems when exact matching is impossible, e.g., when the number of vertices in the two graphs are different. In this case it is required to find the best possible match. For example, in

image recognition Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the huma ...

applications, the results of

image segmentation In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects ( sets of pixels). The goal of segmentation is to simpl ...

image processing An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimension ...

typically produces data graphs with the numbers of vertices much larger than in the model graphs data expected to match against. In the case of attributed graphs, even if the numbers of vertices and edges are the same, the matching still may be only inexact. Two categories of search methods are the ones based on identification of possible and impossible pairings of vertices between the two graphs and methods that formulate graph matching as an

optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...

. Graph edit distance is one of

similarity measure In statistics and related fields, a similarity measure or similarity function or similarity metric is a real-valued function that quantifies the similarity between two objects. Although no single definition of a similarity exists, usually such mea ...

s suggested for graph matching.Horst Bunke, Xiaoyi Jang, "Graph Matching and Similarity", in: ''Intelligent Systems and Interfaces'', pp. 281-304 (2000) The class of algorithms is called error-tolerant graph matching.

References

Computational problems in graph theory {{Comp-sci-stub

See also

References