{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:00:04Z","timestamp":1743141604923,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642174926"},{"type":"electronic","value":"9783642174933"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17493-3_3","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T08:41:01Z","timestamp":1291365661000},"page":"4-13","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Complexity Results in Symmetry Breaking"],"prefix":"10.1007","author":[{"given":"Toby","family":"Walsh","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/3-540-56804-2_33","volume-title":"Methodologies for Intelligent Systems","author":"J.F. Puget","year":"1993","unstructured":"Puget, J.F.: On the satisfiability of symmetrical constrained satisfaction problems. In: Komorowski, J., Ra\u015b, Z.W. (eds.) ISMIS 1993. LNCS, vol.\u00a0689, pp. 350\u2013361. Springer, Heidelberg (1993)"},{"key":"3_CR2","unstructured":"Crawford, J., Ginsberg, M., Luks, G., Roy, A.: Symmetry breaking predicates for search problems. In: Proceedings of the 5th International Conference on Knowledge Representation and Reasoning (KR 1996), pp. 148\u2013159 (1996)"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-642-15246-7_4","volume-title":"PRICAI 2010: Trends in Artificial Intelligence","author":"T. Walsh","year":"2010","unstructured":"Walsh, T.: Symmetry within and between solutions. In: Zhang, B.-T., Orgun, M.A. (eds.) PRICAI 2010. LNCS, vol.\u00a06230, pp. 11\u201313. Springer, Heidelberg (2010)"},{"key":"3_CR4","series-title":"Frontiers in Artificial Intelligence and Applications","first-page":"861","volume-title":"Proceedings of 19th European Conference on Artificial Intelligence, ECAI 2010","author":"G. Katsirelos","year":"2010","unstructured":"Katsirelos, G., Walsh, T.: Symmetries of symmetry breaking constraints. In: Coelho, H., Studer, R., Wooldridge, M. (eds.) Proceedings of 19th European Conference on Artificial Intelligence, ECAI 2010. Frontiers in Artificial Intelligence and Applications, vol.\u00a0215, pp. 861\u2013866. IOS Press, Amsterdam (2010)"},{"key":"3_CR5","volume-title":"Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010","author":"M. Heule","year":"2010","unstructured":"Heule, M., Walsh, T.: Symmetry in solutions. In: Fox, M., Poole, D. (eds.) Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010. AAAI Press, Menlo Park (2010)"},{"key":"3_CR6","unstructured":"Walsh, T.: Breaking value symmetry. In: Fox, D., Gomes, C. (eds.) Proceedings of the 23rd National Conference on AI, Association for Advancement of Artificial Intelligence, pp. 1585\u20131588 (2008)"},{"key":"3_CR7","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/11941439_4","volume-title":"AI 2006: Advances in Artificial Intelligence","author":"T. Walsh","year":"2006","unstructured":"Walsh, T.: Symmetry breaking. In: Sattar, A., Kang, B.-h. (eds.) AI 2006. LNCS (LNAI), vol.\u00a04304, pp. 7\u20138. Springer, Heidelberg (2006)"},{"key":"3_CR8","unstructured":"Gent, I., Walsh, T.: CSPLib: a benchmark library for constraints. Technical report, Technical report APES-09-1999, A shorter version appears in the Proceedings of the 5th International Conference on Principles and Practices of Constraint Programming, CP 1999 (1999)"},{"volume-title":"Handbook of Constraint Programming","year":"2006","key":"3_CR9","unstructured":"Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, Amsterdam (2006)"},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/978-3-540-48085-3_24","volume-title":"Principles and Practice of Constraint Programming \u2013 CP\u201999","author":"F. Pachet","year":"1999","unstructured":"Pachet, F., Roy, P.: Automatic generation of music programs. In: Jaffar, J. (ed.) CP 1999. LNCS, vol.\u00a01713, pp. 331\u2013345. Springer, Heidelberg (1999)"},{"key":"3_CR11","unstructured":"Bessiere, C., Hebrard, E., Hnich, B., Walsh, T.: The complexity of global constraints. In: Proceedings of the 19th National Conference on AI, Association for Advancement of Artificial Intelligence (2004)"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1007\/978-3-540-30201-8_53","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2004","author":"C. Bessi\u00e8re","year":"2004","unstructured":"Bessi\u00e8re, C., Hebrard, E., Hnich, B., Walsh, T.: The tractability of global constraints. In: Wallace, M. (ed.) CP 2004. LNCS, vol.\u00a03258, pp. 716\u2013720. Springer, Heidelberg (2004)"},{"issue":"4","key":"3_CR13","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10601-006-9001-9","volume":"11","author":"C. Bessi\u00e8re","year":"2006","unstructured":"Bessi\u00e8re, C., Hebrard, E., Hnich, B., Kiziltan, Z., Walsh, T.: Filtering algorithms for the NVALUE constraint. Constraints\u00a011(4), 271\u2013293 (2006)","journal-title":"Constraints"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Bessi\u00e8re, C., Hebrard, E., Hnich, B., Kiziltan, Z., Walsh, T.: Filtering algorithms for the NVALUE constraint. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2nd International Conference (CPAIOR 2005) (2005)","DOI":"10.1007\/11493853_8"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity: A framework for systematically confronting computational intractability. In: Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a049, pp. 49\u201399 (1999)","DOI":"10.1090\/dimacs\/049\/04"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1007\/11889205_46","volume-title":"Principles and Practice of Constraint Programming - CP 2006","author":"T. Walsh","year":"2006","unstructured":"Walsh, T.: General symmetry breaking constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol.\u00a04204, pp. 650\u2013664. Springer, Heidelberg (2006)"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-03251-6_6","volume-title":"Recent Advances in Constraints","author":"G. Katsirelos","year":"2009","unstructured":"Katsirelos, G., Narodytska, N., Walsh, T.: Combining symmetry breaking and global constraints. In: Oddi, A., Fages, F., Rossi, F. (eds.) Recent Advances in Constraints. LNCS, vol.\u00a05655, pp. 84\u201398. Springer, Heidelberg (2009)"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-540-74970-7_31","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2007","author":"Y.C. Law","year":"2007","unstructured":"Law, Y.C., Lee, J., Walsh, T., Yip, J.: Breaking symmetry of interchangeable variables and values. In: Bessi\u00e8re, C. (ed.) CP 2007. LNCS, vol.\u00a04741, pp. 423\u2013437. Springer, Heidelberg (2007)"},{"key":"3_CR19","unstructured":"Hnich, B., Kiziltan, Z., Walsh, T.: Combining symmetry breaking with other constraints: lexicographic ordering with sums. In: Proceedings of the 8th International Symposium on the Artificial Intelligence and Mathematics (2004)"},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-46135-3_7","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"A. Frisch","year":"2002","unstructured":"Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Global constraints for lexicographic orderings. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, p. 93. Springer, Heidelberg (2002)"},{"issue":"10","key":"3_CR21","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1016\/j.artint.2006.03.002","volume":"170","author":"A. Frisch","year":"2006","unstructured":"Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Propagation algorithms for lexicographic ordering constraints. Artificial Intelligence\u00a0170(10), 803\u2013908 (2006)","journal-title":"Artificial Intelligence"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/11564751_37","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"J.F. Puget","year":"2005","unstructured":"Puget, J.F.: Breaking all value symmetries in surjection problems. In: van Beek, P. (ed.) CP 2005. LNCS, vol.\u00a03709, pp. 490\u2013504. Springer, Heidelberg (2005)"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1007\/978-3-540-74970-7_67","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2007","author":"T. Walsh","year":"2007","unstructured":"Walsh, T.: Breaking value symmetry. In: Bessi\u00e8re, C. (ed.) CP 2007. LNCS, vol.\u00a04741, pp. 880\u2013887. Springer, Heidelberg (2007)"},{"key":"3_CR24","unstructured":"Bessi\u00e8re, C., Hebrard, E., Hnich, B., Kiziltan, Z., Quimper, C.G., Walsh, T.: The parameterized complexity of global constraints. In: Fox, D., Gomes, C. (eds.) Proceedings of the 23rd National Conference on AI, Association for Advancement of Artificial Intelligence, pp. 235\u2013240 (2008)"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Aloul, F., Ramani, A., Markov, I., Sakallah, K.: Solving difficult SAT instances in the presence of symmetries. In: Proceedings of the Design Automation Conference, pp. 731\u2013736 (2002)","DOI":"10.1145\/513918.514102"},{"key":"3_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/978-3-540-30201-8_28","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2004","author":"Y. Law","year":"2004","unstructured":"Law, Y., Lee, J.: Global constraints for integer and set value precedence. In: Wallace, M. (ed.) CP 2004. LNCS, vol.\u00a03258, pp. 362\u2013376. Springer, Heidelberg (2004)"},{"key":"3_CR27","series-title":"Frontiers in Artificial Intelligence and Applications","first-page":"168","volume-title":"Proceedings of Including Prestigious Applications of Intelligent Systems (PAIS 2006)","author":"T. Walsh","year":"2006","unstructured":"Walsh, T.: Symmetry breaking using value precedence. In: Brewka, G., Coradeschi, S., Perini, A., Traverso, P. (eds.) Proceedings of Including Prestigious Applications of Intelligent Systems (PAIS 2006), Riva del Garda, Italy, August 29-September 1. Frontiers in Artificial Intelligence and Applications, vol.\u00a0141, pp. 168\u2013172. IOS Press, Amsterdam (2006)"},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/3-540-46135-3_31","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"P. Flener","year":"2002","unstructured":"Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Breaking row and column symmetry in matrix models. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, p. 462. Springer, Heidelberg (2002)"},{"key":"3_CR29","unstructured":"Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Matrix modelling. Technical Report APES-36-2001, APES group, Presented at Formul, Workshop on Modelling and Problem Formulation, CP 2001 post-conference workshop (2001)"},{"key":"3_CR30","unstructured":"Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Matrix modelling: Exploiting common patterns in constraint programming. In: Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems, held alongside CP 2002 (2002)"},{"key":"3_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-540-45193-8_4","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"T. Walsh","year":"2003","unstructured":"Walsh, T.: Constraint patterns. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 53\u201364. Springer, Heidelberg (2003)"},{"key":"3_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-642-04244-7_7","volume-title":"Principles and Practice of Constraint Programming - CP 2009","author":"S. Huczynska","year":"2009","unstructured":"Huczynska, S., McKay, P., Miguel, I., Nightingale, P.: Modelling equidistant frequency permutation arrays: An application of constraints to mathematics. In: Gent, I.P. (ed.) CP 2009. LNCS, vol.\u00a05732, pp. 50\u201364. Springer, Heidelberg (2009)"},{"key":"3_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-642-15396-9_26","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2010","author":"G. Katsirelos","year":"2010","unstructured":"Katsirelos, G., Narodytska, N., Walsh, T.: On the complexity and completeness of static constraints for breaking row and column symmetry. In: Cohen, D. (ed.) CP 2010. LNCS, vol.\u00a06308, pp. 305\u2013320. Springer, Heidelberg (2010)"},{"key":"3_CR34","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/S1571-0653(04)00311-7","volume":"9","author":"I. Shlyakhter","year":"2001","unstructured":"Shlyakhter, I.: Generating effective symmetry-breaking predicates for search problems. Electronic Notes in Discrete Mathematics\u00a09, 19\u201335 (2001)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"3_CR35","unstructured":"Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Symmetry in matrix models. Technical Report APES-30-2001, APES group, Presented at SymCon 2001 (Symmetry in Constraints), CP 2001 post-conference workshop (2001)"},{"issue":"1","key":"3_CR36","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E. Freuder","year":"1982","unstructured":"Freuder, E.: A sufficient condition for backtrack-free search. Journal of the Association for Computing Machinery\u00a029(1), 24\u201332 (1982)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR37","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R. Dechter","year":"1989","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artificial Intelligence\u00a038, 353\u2013366 (1989)","journal-title":"Artificial Intelligence"},{"key":"3_CR38","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0004-3702(94)90021-3","volume":"65","author":"M. Cooper","year":"1994","unstructured":"Cooper, M., Cohen, D., Jeavons, P.: Characterizing tractable constraints. Artificial Intelligence\u00a065, 347\u2013361 (1994)","journal-title":"Artificial Intelligence"},{"key":"3_CR39","unstructured":"Bessiere, C., R\u00e9gin, J.: Arc consistency for general constraint networks: Preliminary results. In: Proceedings of the 15th International Conference on AI, International Joint Conference on Artificial Intelligence, pp. 398\u2013404 (1997)"},{"key":"3_CR40","unstructured":"R\u00e9gin, J.C.: A filtering algorithm for constraints of difference in CSPs. In: Proceedings of the 12th National Conference on AI, Association for Advancement of Artificial Intelligence, pp. 362\u2013367 (1994)"},{"key":"3_CR41","doi-asserted-by":"crossref","unstructured":"Samer, M., Szeider, S.: Tractable cases of the extended global cardinality constraint. In: Proceedings of CATS 2008, Computing: The Australasian Theory Symposium (2008)","DOI":"10.1007\/s10601-009-9077-0"},{"issue":"2","key":"3_CR42","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00224-004-1192-0","volume":"38","author":"S. Szeider","year":"2005","unstructured":"Szeider, S.: The complexity of resolution with generalized symmetry rules. Theory of Computing Systems\u00a038(2), 171\u2013188 (2005)","journal-title":"Theory of Computing Systems"},{"volume-title":"Handbook of Satisfiability","year":"2009","key":"3_CR43","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. IOS Press, Amsterdam (2009)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17493-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T15:39:15Z","timestamp":1559835555000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17493-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642174926","9783642174933"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17493-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}