Affordable Access

Bounds of graph parameters for global constraints

Publication Date
  • Computer Science
  • Linguistics
  • Mathematics


PDF/04/ro0652.pdf.url RAIRO Operations Research 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 Abstract. This article presents a basic scheme for deriving system- atically a filtering algorithm from the graph properties based represen- tation 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. Keywords. Global constraint, graph constraint, filtering, bound. Mathematics Subject Classification. 68R01. 1. Introduction One of the main objectives of constraint programming is to provide generic tools for solving combinatorial problems, notably AC algorithms [9,14,18], general purpose combinators [15], and automata for characterizing the solutions of a con- straint [4,20,30]. To deal with real-world problems, various global constraints with ad-hoc filtering algorithms, usually based on graph theory [16,17,23–26,28], have been introduced. In [8], Bessie`re and Van Hentenryck proposed several definitions of the notion of globality. They introduced the notion of “semantic globality (ex- pressiveness), operational globality (quality of filtering), and algorithmic globality (computational efficiency of the filtering)”. Beldiceanu presented in [2] a system- atic description of these global constraints in terms of graph properties: among the 234 constraints of the catalog of global constraints [5], about 200 constraints are described as a conjunction of graph properties where each graph property has Received November 16, 2006. Accepted November 20, 2006. 1 E´cole des Mines de Nantes, LINA FRE CNRS 2729, 44307 Nantes, France; [email protected]; [email protected] 2 Bouygues e-lab, 78061 St Quentin en Yvelines, France; [email protected] c© EDP Sciences, ROADEF, SMAI 2007 Article published by EDP Sciences and

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times