Beldiceanu, Nicolas and Carlsson, Mats and Demassey, Sophie and Petit, Thierry (2006) *Graph Properties Based Filtering.* [SICS Report]

| PDF 418Kb | |

Postscript 285Kb |

## Abstract

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