Graph Properties Based Filtering
Number of Authors: 4
2006 (English)Report (Refereed)
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.
Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2006, 1. , 30 p.
SICS Technical Report, ISSN 1100-3154 ; 2006:10
Constraint Programming, Global Constraints, Filtering Algorithms, Graph Properties
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22023OAI: oai:DiVA.org:ri-22023DiVA: diva2:1041565