Cogprints

A Necessary and Sufficient Condition for Graph Matching to be equivalent to Clique Search

Jain, Brijnesh (2009) A Necessary and Sufficient Condition for Graph Matching to be equivalent to Clique Search. [Preprint]

Full text available as:

[img]
Preview
PDF - Draft Version
422Kb

Abstract

This paper formulates a necessary and sufficient condition for a generic graph matching problem to be equivalent to the maximum vertex and edge weight clique problem in a derived association graph. The consequences of this results are threefold: first, the condition is general enough to cover a broad range of practical graph matching problems; second, a proof to establish equivalence between graph matching and clique search reduces to showing that a given graph matching problem satisfies the proposed condition; and third, the result sets the scene for generic continuous solutions for a broad range of graph matching problems. To illustrate the mathematical framework, we apply it to a number of graph matching problems, including the problem of determining the graph edit distance.

Item Type:Preprint
Keywords:graph matching, maximum weight clique problem
Subjects:Computer Science > Artificial Intelligence
ID Code:6751
Deposited By: Jain, Brijnesh
Deposited On:19 Dec 2009 11:47
Last Modified:11 Mar 2011 08:57

Metadata

Repository Staff Only: item control page