@Article{	  larrosa.valiente:mscs:2002,
  author	= {Javier Larrosa and Gabriel Valiente},
  title		= {Constraint Satisfaction Algorithms for Graph Pattern
		  Matching},
  journal	= {Mathematical Structures in Computer Science},
  volume	= 12,
  number	= 4,
  year		= 2002,
  pages		= {403--422},
  abstract	= {Graph pattern matching is a central problem in many
		  application fields. Since it is NP-complete, we cannot
		  expect to find algorithms with a good worst-case
		  performance. However, there is still room for general
		  procedures with a good average performance. In this paper
		  we explore four different solving approaches within the
		  constraint satisfaction framework, and introduce a new
		  algorithm, which we call nRF+. The algorithm is a
		  refinement of really full look ahead that takes advantage
		  of the problem structure in order to enhance the look ahead
		  procedure. We give a formal proof that nRF+ is superior to
		  the other approaches in terms of number of visited nodes.
		  An additional contribution of this paper is the
		  introduction of a new benchmark for testing algorithms in
		  this domain. It is formed by a large set of well-defined
		  graphs of very diverse nature. In this benchmark, we show
		  that nRF+ can efficiently solve a broad range of problems,
		  while still leaving many problem instances unsolved. The
		  use of this challenging benchmark is encouraged for future
		  algorithms evaluation.}
}