Beldiceanu, Nicolas and Carlsson, Mats and Demassey, Sophie and Petit, Thierry (2006) Graph Properties Based Filtering. [SICS Report]
This report presents a generic filtering scheme, based on the graph description of global constraints. This description is defined by a network of binary constraints and a list of elementary graph properties: each solution of the global constraint corresponds to a subgraph of the initial network, retaining only the satisfied binary constraints, and which fulfills all the graph properties. The graph-based filtering identifies the arcs of the network that belong or not to the solution subgraphs. The objective is to build, besides a catalog of global constraints, also a list of systematic filtering rules based on a limited set of graph properties. We illustrate this principle on some common graph properties and provide computational experiments of the effective filtering on the "group" constraint.
|Item Type:||SICS Report|
|Uncontrolled Keywords:||Constraint Programming, Global Constraints, Filtering Algorithms, Graph Properties|
|Deposited By:||Vicki Carleson|
|Deposited On:||29 Oct 2007|
|Last Modified:||18 Nov 2009 16:04|
Repository Staff Only: item control page