creators_name: Jain, Brijnesh
creators_id: jbj@cs.tu-berlin.de
type: preprint
datestamp: 2009-12-19 11:47:59
lastmod: 2011-03-11 08:57:34
metadata_visibility: show
title: A Necessary and Sufficient Condition for Graph Matching to be equivalent to Clique Search
subjects: comp-sci-art-intel
full_text_status: public
keywords: graph matching, maximum weight clique problem
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.
date: 2009-12-15
date_type: published
refereed: FALSE
citation:   Jain, Brijnesh  (2009) A Necessary and Sufficient Condition for Graph Matching to be equivalent to Clique Search.  [Preprint]     
document_url: http://cogprints.org/6751/1/pami2.pdf