Constraint models for graceful graphs
Tóm tắt
We present three constraint models of the problem of finding a graceful labelling of a graph, or proving that the graph is not graceful. An experimental comparison of the models applied to different classes of graph is given. The first model seems a natural way to represent the problem, but explores a much larger search tree than the other models. The second model does much less search, by making the most constrained decisions first, but is slow because the constraints are time-consuming to propagate. The third model combines the best features of the others, doing little more search than the second model while being much the fastest of the three. The comparison of the three models provides a useful case-study of modelling problems as constraint satisfaction problems. In addition, we show that constraint programming can be a useful tool for the study of graceful graphs; the models presented here have contributed many new results.
Tài liệu tham khảo
Beldiceanu, N. (2000). Global constraints as graph properties on structured network of elementary constraints of the same type. Technical report T2000/01, SICS.
Bermond, J. C., & Farhi, G. (1982). Sur un problème combinatoire d’antennes en radioastronomie II. Annals of Discrete Mathematics, 12, 49–53.
Bessière, C. (2006). Constraint propagation. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (Chapter 3, pp. 19–73). Amsterdam: Elsevier.
Bessière, C., & Régin, J. (1999). Enforcing arc consistency on global constraints by solving subproblems on the fly. In Proceedings CP’99 (pp. 103–117).
Bessière, C., & Régin, J.-C. (1997). Arc consistency for general constraint networks: Preliminary results. In Proceedings IJCAI’97 (Vol. 1, pp. 398–404).
Beutner, D., & Harborth, H. (2002). Graceful labelings of nearly complete graphs. Results in Mathematics, 41, 34–39.
Cheng, B. M. W., Choi, K. M. F., Lee, J. H. M., & Wu, J. C. K. (1999). Increasing constraint propagation by redundant modeling: An experience report. Constraints, 4, 167–192.
Cohen, D., Jeavons, P., Jefferson, C., Petrie, K. E., & Smith, B. M. (2006). Symmetry definitions for constraint programming. Constraints, 11, 115–137.
Crawford, J., Ginsberg, M., Luks, E., & Roy, A. (1996). Symmetry-breaking predicates for search problems. In Proceedings KR’96 (pp. 149–159), Nov. 1996.
Gallian, J. A. (2008). A dynamic survey of graph labeling. The Electronic Journal of Combinatorics, (DS6), 11th edition. www.combinatorics.org.
Gent, I. P., Irving, R. W., Manlove, D., Prosser, P., & Smith, B. M. (2001). A constraint programming approach to the stable marriage problem. In T. Walsh (Ed.), Principles and practice of constraint programming - CP 2001. LNCS (Vol. 2239, pp. 225–239). New York: Springer.
Gent, I. P., & Smith, B. M. (2000). Symmetry breaking during search in constraint programming. In W. Horn (Ed.), Proceedings ECAI’2000, the European conference on artificial intelligence (pp. 599–603).
Golomb, S. W. (1972). How to number a graph. In R. C. Read (Ed.), Graph theory and computing (pp. 23–37). New York: Academic.
Hnich, B., Smith, B. M., & Walsh, T. (2004). Dual models of permutation and injection problems. Journal of Artificial Intelligence Research, 21, 357–391.
ILOG S.A., Gentilly, France (2007). Solver 6.4 reference manual. ILOG S.A., May 2007.
Law, Y. C., & Lee, J. H. M. (2006). Symmetry breaking constraints for value symmetries in constraint satisfaction. Constraints, 11, 221–267.
Lustig, I. J., & Puget, J.-F. (2001). Program does not equal program: Constraint programming and its relationship to mathematical programming. INTERFACES, 31(6), 29–53.
Petrie, K. E., & Smith, B. M. (2003). Symmetry breaking in graceful graphs. Technical report APES-56-2003, APES Research Group. Available from http://www.dcs.st-and.ac.uk/∼apes/apesreports.html.
Puget, J.-F. (2005). Breaking symmetries in all different problems. In Proceedings of IJCAI’05 (pp. 272–277).
Puget, J.-F. (2006). An efficient way of breaking value symmetries. In Proceedings of the 21st national conference on artificial intelligence (AAAI-06) (pp. 117–122). Cambridge: AAAI.
Puget, J.-F. (2006). Dynamic lex constraints. In F. Benhamou (Ed.), Principles and practice of constraint programming - CP 2006, LNCS 4204. New York: Springer.
Puget, J.-F., & Smith, B. M. (2006). Improved models for graceful graphs. In Proceedings of the CP 2006 workshop on modelling and solving problems with constraints.
Régin, J.-C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings AAAI’94 (Vol. 1, pp. 362–367).
Smith, B., & Petrie, K. (2003). Graceful graphs: Results from constraint programming. http://www.comp.leeds.ac.uk/bms/Graceful/.
Smith, B. M. (2005). Symmetry and search in a network design problem. In R. Bartak, & M. Milano (Eds.), Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, proceedings of CPAIOR 2005 (2nd international conference). LNCS (Vol. 3524, pp. 336–350). New York: Springer.
Smith, B. M. (2006). Constraint programming models for graceful graphs. In F. Benhamou (Ed.), Principles and practice of constraint programming - CP 2006, LNCS (Vol. 4204, pp. 545–559). New York: Springer.
van Beek, P. (2006). Constraint propagation. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (Chapter 4, pp. 75–124). Amsterdam: Elsevier.