# Bounds of graph parameters for global constraints

Nicolas Beldiceanu; Thierry Petit; Guillaume Rochart

RAIRO - Operations Research (2007)

- Volume: 40, Issue: 4, page 327-353
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBeldiceanu, Nicolas, Petit, Thierry, and Rochart, Guillaume. "Bounds of graph parameters for global constraints." RAIRO - Operations Research 40.4 (2007): 327-353. <http://eudml.org/doc/105353>.

@article{Beldiceanu2007,

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.
},

author = {Beldiceanu, Nicolas, Petit, Thierry, Rochart, Guillaume},

journal = {RAIRO - Operations Research},

keywords = {Global constraint; graph constraint; filtering; bound.; global constraint},

language = {eng},

month = {2},

number = {4},

pages = {327-353},

publisher = {EDP Sciences},

title = {Bounds of graph parameters for global constraints},

url = {http://eudml.org/doc/105353},

volume = {40},

year = {2007},

}

TY - JOUR

AU - Beldiceanu, Nicolas

AU - Petit, Thierry

AU - Rochart, Guillaume

TI - Bounds of graph parameters for global constraints

JO - RAIRO - Operations Research

DA - 2007/2//

PB - EDP Sciences

VL - 40

IS - 4

SP - 327

EP - 353

AB -
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.

LA - eng

KW - Global constraint; graph constraint; filtering; bound.; global constraint

UR - http://eudml.org/doc/105353

ER -

## References

top- P. Baptiste, C. Le Pape and L. Peridy, Global Constraints for Partial CSPs: A Case-Study of Resource and Due Date Constraints, in Principles and Practice of Constraint Programming (CP'98), edited by M. Maher and J.-F. Puget, Springer-Verlag, Lect. Notes Comput. Sci.1520 (1998) 87–101.
- N. Beldiceanu, Global Constraints as Graph Properties on a Structured Network of Elementary Constraints of the Same Type, in Principles and Practice of Constraint Programming (CP'2000), edited by R. Dechter, Springer-Verlag, Lect. Notes Comput. Sci.1894 (2000) 52–66. Preprint available as SICS Tech Report T2000-01. Zbl1044.68737
- N. Beldiceanu, Global Constraints as Graph Properties on Structured Network of Elementary Constraints of the Same Type. Technical Report T2000-01, Swedish Institute of Computer Science (2000). Zbl1044.68737
- N. Beldiceanu, M. Carlsson and T. Petit, Deriving Filtering Algorithms from Constraint Checkers, in Principles and Practice of Constraint Programming (CP'2004), edited by M. Wallace, Springer-Verlag, Lect. Notes Comput. Sci.3258 (2004) 107–122. Preprint available as SICS Tech Report T2004-08. Zbl1152.68539
- N. Beldiceanu, M. Carlsson and J.-X. Rampon, Global Constraint Catalog. Technical Report T2005-08, Swedish Institute of Computer Science (2005).
- N. Beldiceanu and T. Petit, Cost Evaluation of Soft Global Constraints, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR 2004), edited by J.-C. Régin and M. Rueher, Springer-Verlag, Lect. Notes Comput. Sci.3011 (2004) 80–95.
- C. Bessière, E. Hebrard, B. Hnich, Z. Kızıltan and T. Walsh, Filtering Algorithms for the nvalue Constraint, in International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR'05), Prague, Czech Republic, edited by R. Barták and M. Milano, Springer-Verlag, Lect. Notes Comput. Sci.3524 (2005) 79–93 Zbl1133.68427
- C. Bessière and P. Van Hentenryck, To Be or not to Be... a Global Constraint, in Principles and Practice of Constraint Programming (CP'2003), edited by F. Rossi, Springer-Verlag, Lect. Notes Comput. Sci.2833 (2003) 789–794. Zbl1273.68334
- C. Bessière and J.-C. Régin, Refining the Basic Constraint Propagation Algorithm, in Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001, edited by B. Nebel, Morgan Kaufmann (2001) 309–315.
- G. Dooms, Y. Deville and P. Dupont, CP(Graph): Introducing a Graph Computation Domain in Constraint Programming, in Principles and Practice of Constraint Programming (CP'2005), edited by P. van Beek, Springer-Verlag, Lect. Notes Comput. Sci.3709 (2005) 211–225. Zbl1153.68457
- E.C. Freuder and R.J. Wallace, Partial constraint satisfaction. Artificial Intelligence58 (1992) 21–70.
- M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company (1979). Zbl0411.68039
- D. Hanák, Implementing Global Constraints as Structured Graphs of Elementary Constraints. Scientific Journal Acta Cybernetica16 (2003) 241–258. Zbl1049.68030
- P. Van Hentenryck, Y. Deville and C.M. Teng, A Generic Arc Consistency Algorithm and its Specializations. Artificial Intelligence57 (1992) 291–321. Zbl0763.68059
- P. Van Hentenryck, V. Saraswat and Y. Deville, Design, implementation, and evaluation of the constraint language cc(FD). J. Logic Programming37 (1998) 139–164. Zbl0920.68026
- I. Katriel and S. Thiel, Fast Bound Consistency for the global cardinality Constraint, in Principles and Practice of Constraint Programming (CP'2003), edited by F. Rossi, Springer-Verlag, Lect. Notes Comput. Sci.2833 (2003) 437–451. Zbl1273.68400
- K. Mehlhorn and S. Thiel, Faster Algorithms for Bound-Consistency of the sortedness and the alldifferent Constraint, in Principles and Practice of Constraint Programming (CP'2000), edited by R. Dechter, Springer-Verlag, Lect. Notes Comput. Sci.1894 (2000) 306–319. Zbl1044.68783
- U. Montanari, Networks of constraints: Fundamental properties and applications to picture processing. Information Science7 (1974) 95–132. Zbl0284.68074
- R.Z. Norman and M.O. Rabin, An algorithm for minimum cover of a graph. American Math. Soc.10 (1959) 315–319. Zbl0093.37702
- G. Pesant, A Regular Language Membership Constraint for Finite Sequences of Variables, in Principles and Practice of Constraint Programming (CP'2004) edited by M. Wallace, Springer-Verlag, Lect. Notes Comput. Sci.3258 (2004) 482–495. Zbl1152.68573
- T. Petit, J-C. Régin and C. Bessière, Meta constraints on violations for over constrained problems, in 12th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2000), 13-15 November 2000, Vancouver, BC, Canada, IEEE Computer Society (2000) 358–365.
- T. Petit, J-C. Régin and C. Bessière, Specific filtering algorithms for over constrained problems, in Principles and Practice of Constraint Programming (CP'2001), edited by T. Walsh, Springer-Verlag, Lect. Notes Comput. Sci.2239 (2001) 451–463. Zbl1067.68663
- C.-G. Quimper, A. López-Ortiz, P. van Beek and A. Golynski, Improved Algorithms for the global cardinality Constraint, in Principles and Practice of Constraint Programming (CP'2004), edited by M. Wallace, Springer-Verlag, Lect. Notes Comput. Sci.3258 (2004) 542–556. Zbl1152.68576
- J.-C. Régin, A Filtering Algorithm for Constraints of Difference in CSP, in 12th National Conference on Artificial Intelligence (AAAI-94) (1994) 362–367.
- J.-C. Régin, Generalized Arc Consistency for global cardinality Constraint, in 14th National Conference on Artificial Intelligence (AAAI-96) (1996) 209–215.
- J.-C. Régin, The Symmetric alldiff Constraint, in 16th Int. Joint Conf. on Artificial Intelligence (IJCAI-99) (1999) 420–425.
- P. Turán, On an Extremal Problem in Graph Theory. Mat. Fiz. Lapok48 (1941) 436–452, in Hungarian.
- W.-J. van Hoeve, A Hyper-Arc Consistency Algorithm for the soft alldifferent Constraint, in Principles and Practice of Constraint Programming (CP'2004), edited by M. Wallace, Springer-Verlag, Lect. Notes Comput. Sci.3258 (2004) 679–689.
- W.-J. van Hoeve, G. Pesant and L.-M. Rousseau, On global warming: Flow-based soft global constraints, in Journal of Heuristics12 (2006) 347–373. Zbl1100.68623
- N.R. Vempaty, Solving Constraint Satisfaction Problems using Finite State Automata, in National Conference on Artificial Intelligence (AAAI-92), AAAI Press (1992) 453–458.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.