@TechReport{Zampelli:Mann:DDSgraph:INGI2008,
  author =	 {Stephane Zampelli and Martin Mann and Yves Deville and Rolf Backofen},
  title =	 {Decomposition Techniques for Subgraph Matching},
  pages =	 15,
  year =	 2008,
  user =	 {mmann},
  institution =  {Universite catholique de Louvain},
  note =     {INGI2008/03},
  arxiv =    {0805.1030v1},
  abstract =	 {In the constraint programming framework, state-of-the-art
static and dynamic decomposition techniques are hard to apply to prob-
lems with complete initial constraint graphs. For such problems, we pro-
pose a hybrid approach of these techniques in the presence of global
constraints. In particular, we solve the subgraph isomorphism problem.
Further we design specific heuristics for this hard problem, exploiting its
special structure to achieve decomposition. The underlying idea is to pre-
compute a static heuristic on a subset of its constraint network, to follow
this static ordering until a first problem decomposition is available, and
to switch afterwards to a fully propagated, dynamically decomposing
search. Experimental results show that, for sparse graphs, our decom-
position method solves more instances than dedicated, state-of-the-art
matching algorithms or standard constraint programming approaches.}
}