Graph Properties Based Filtering

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
ID Code:2301
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:04

Repository Staff Only: item control page