This site has been permanently archived. This is a static copy provided by the University of Southampton.

TY - GEN ID - cogprints6751 UR - http://cogprints.org/6751/ A1 - Jain, Brijnesh TI - A Necessary and Sufficient Condition for Graph Matching to be equivalent to Clique Search Y1 - 2009/12/15/ N2 - 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. AV - public KW - graph matching KW - maximum weight clique problem ER -