A constraint programming approach to subgraph isomorphism
This thesis proposes an expressive yet efficient declarative framework
for graph matching in constraint programming (CP), and focuses
on efficient algorithms to solve the subgraph isomorphism problem.
The framework is based on graph and map variables, and
specific graph morphism constraints.
This allows to model and solve various graph matching problems,
avoiding the tedious development of dedicated and specific
A specialized filtering algorithm is proposed for the subgraph
which uses the semantic
of the problem as well as the global structure of the two input graphs.
It is shown that it is the state-of-the-art filtering algorithm,
dedicated algorithms and other CP approaches.
Various search techniques from CP are also extended to the subgraph
An automatic detection and exploitation
of symmetries for the subgraph isomorphism problem is proposed, together
a decomposition approach of the search.
The significance of this thesis lies in the fact that, even though the
framework is expressive,
CP can be considered as the state-of-the-art for subgraph isomorphism,
outperforming the dedicated known algorithms on current benchmarks.
School:Université catholique de Louvain
Source Type:Master's Thesis
Keywords:isomorphism matching graph constraint programming subgraph
Date of Publication:06/24/2008