Change search
ReferencesLink to record
Permanent link

Direct link
Graph Properties Based Filtering
Number of Authors: 4
2006 (English)Report (Refereed)
Abstract [en]

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
Keyword [en]
Constraint Programming, Global Constraints, Filtering Algorithms, Graph Properties
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-14211OAI: diva2:1035499
Available from: 2016-10-13 Created: 2016-10-13

Open Access in DiVA

fulltext(419 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 419 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link