Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Graph Matching

Keywords: Relational structures, double subgraph isomorphism, graph isomorphism, matching

Categories: Natural Language , Vision

Author(s): H.W. Hughes

Relational structures are often represented as graphs with nodes connected by labelled arcs. The problem of matching two such structures is known as graph matching and can be achieved in a number of ways. Firstly a one-to-one mapping can be achieved between the nodes and arcs of each of the two graphs. This is known as graph isomorphism. Alternatively a one-to-one mapping can be achieved between one graph and a subgraph of the other. This is known as double subgraph isomorphism. Sometimes a perfect mapping between graphs is not required, some arcs and nodes being considered unimportant and omitted from the matching process.



Add Comment

No comments.