Bounds of graph parameters for global constraints

 Access to full text

 Full (PDF)

1. [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. [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. [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. [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. [5] N. Beldiceanu, M. Carlsson and J.-X. Rampon, Global Constraint Catalog. Technical Report T2005-08, Swedish Institute of Computer Science (2005). 
6. [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. [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. [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. [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. [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. [11] E.C. Freuder and R.J. Wallace, Partial constraint satisfaction. Artificial Intelligence 58 (1992) 21–70. 
12. [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. [13] D. Hanák, Implementing Global Constraints as Structured Graphs of Elementary Constraints. Scientific Journal Acta Cybernetica 16 (2003) 241–258. Zbl1049.68030
14. [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. [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. [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. [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. [18] U. Montanari, Networks of constraints: Fundamental properties and applications to picture processing. Information Science 7 (1974) 95–132. Zbl0284.68074
19. [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. [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. [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. [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. [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. [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. [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. [26] J.-C. Régin, The Symmetric alldiff Constraint, in 16th Int. Joint Conf. on Artificial Intelligence (IJCAI-99) (1999) 420–425. 
27. [27] P. Turán, On an Extremal Problem in Graph Theory. Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian. Zbl0026.26903
28. [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. [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. [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.