EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO Oper. Res.
Volume 40, Number 4, October-December 2006
Journées Francophones de Programmation par Contraintes 2005
Page(s) 327 - 353
DOI 10.1051/ro:2007001
Published online 14 February 2007

RAIRO Oper. Res. 40 (2006) 327-353
DOI: 10.1051/ro:2007001

Bounds of graph parameters for global constraints

Nicolas Beldiceanu1, Thierry Petit1 and Guillaume Rochart2

1  École des Mines de Nantes, LINA FRE CNRS 2729, 44307 Nantes, France; Nicolas.Beldiceanu@emn.fr; Thierry.Petit@emn.fr
2  Bouygues e-lab, 78061 St Quentin en Yvelines, France; Grochart@bouygues.com

(Received November 16, 2006. Accepted November 20, 2006 Published online 14 February 2007.)

Abstract
This article presents a basic scheme for deriving systematically a filtering algorithm from the graph properties based representation of global constraints. This scheme is based on the bounds of the graph parameters used in the description of a global constraint. The article provides bounds for the most common used graph parameters.


Mathematics Subject Classification. 68R01.

Key words: Global constraint, graph constraint, filtering, bound.


© EDP Sciences 2007


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.