# Bounds of graph parameters for global constraints

Nicolas Beldiceanu; Thierry Petit; Guillaume Rochart^{[1]}

- [1] Bouygues e-lab, 78061 St Quentin en Yvelines, France

RAIRO - Operations Research - Recherche Opérationnelle (2006)

- 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 - Recherche Opérationnelle 40.4 (2006): 327-353. <http://eudml.org/doc/245769>.

@article{Beldiceanu2006,

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

affiliation = {Bouygues e-lab, 78061 St Quentin en Yvelines, France},

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

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

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

language = {eng},

number = {4},

pages = {327-353},

publisher = {EDP-Sciences},

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

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

volume = {40},

year = {2006},

}

TY - JOUR

AU - Beldiceanu, Nicolas

AU - Petit, Thierry

AU - Rochart, Guillaume

TI - Bounds of graph parameters for global constraints

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2006

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

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

ER -

## References

top- [1] 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.
- [2] 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
- [3] 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
- [4] 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
- [5] N. Beldiceanu, M. Carlsson and J.-X. Rampon, Global Constraint Catalog. Technical Report T2005-08, Swedish Institute of Computer Science (2005).
- [6] 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. Zbl1094.68638
- [7] 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
- [8] 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.
- [9] 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.
- [10] 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
- [11] E.C. Freuder and R.J. Wallace, Partial constraint satisfaction. Artificial Intelligence 58 (1992) 21–70.
- [12] 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.68039MR519066
- [13] D. Hanák, Implementing Global Constraints as Structured Graphs of Elementary Constraints. Scientific Journal Acta Cybernetica 16 (2003) 241–258. Zbl1049.68030
- [14] P. Van Hentenryck, Y. Deville and C.M. Teng, A Generic Arc Consistency Algorithm and its Specializations. Artificial Intelligence 57 (1992) 291–321. Zbl0763.68059
- [15] P. Van Hentenryck, V. Saraswat and Y. Deville, Design, implementation, and evaluation of the constraint language cc(FD). J. Logic Programming 37 (1998) 139–164. Zbl0920.68026
- [16] 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
- [17] 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
- [18] U. Montanari, Networks of constraints: Fundamental properties and applications to picture processing. Information Science 7 (1974) 95–132. Zbl0284.68074
- [19] R.Z. Norman and M.O. Rabin, An algorithm for minimum cover of a graph. American Math. Soc. 10 (1959) 315–319. Zbl0093.37702
- [20] 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.
- [21] 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.
- [22] 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
- [23] 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
- [24] 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.
- [25] J.-C. Régin, Generalized Arc Consistency for global cardinality Constraint, in 14th National Conference on Artificial Intelligence (AAAI-96) (1996) 209–215.
- [26] J.-C. Régin, The Symmetric alldiff Constraint, in 16th Int. Joint Conf. on Artificial Intelligence (IJCAI-99) (1999) 420–425.
- [27] P. Turán, On an Extremal Problem in Graph Theory. Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian. Zbl0026.26903
- [28] 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.
- [29] W.-J. van Hoeve, G. Pesant and L.-M. Rousseau, On global warming: Flow-based soft global constraints, in Journal of Heuristics 12 (2006) 347–373. Zbl1100.68623
- [30] 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.