{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T02:02:20Z","timestamp":1760061740140,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,4,2]],"date-time":"2016-04-02T00:00:00Z","timestamp":1459555200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["182\/13"],"award-info":[{"award-number":["182\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s10601-016-9244-z","type":"journal-article","created":{"date-parts":[[2016,4,2]],"date-time":"2016-04-02T05:08:31Z","timestamp":1459573711000},"page":"357-374","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Breaking symmetries in graph search with canonizing sets"],"prefix":"10.1007","volume":"21","author":[{"given":"Avraham","family":"Itzhakov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Codish","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,2]]},"reference":[{"issue":"2","key":"9244_CR1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1002\/jgt.3190110214","volume":"11","author":"Y Alavi","year":"1987","unstructured":"Alavi, Y., Chartrand, G., Chung, F.R., Erd\u00f6s, P., Graham, R.L., & Oellermann, O.R. (1987). Highly irregular graphs. Journal of Graph Theory, 11(2), 235\u2013249.","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"9244_CR2","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.3390\/sym2021121","volume":"2","author":"FA Aloul","year":"2010","unstructured":"Aloul, F.A. (2010). Symmetry in boolean satisfiability. Symmetry, 2(2), 1121\u20131134. doi: 10.3390\/sym2021121 .","journal-title":"Symmetry"},{"unstructured":"Aloul, F.A., Markov, I.L., Ramani, A., & Sakallah, K.A. (2011). Breaking instance-independent symmetries in exact graph coloring. CoRR 1109.2347 .","key":"9244_CR3"},{"issue":"5","key":"9244_CR4","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/TC.2006.75","volume":"55","author":"FA Aloul","year":"2006","unstructured":"Aloul, F.A., Sakallah, K.A., & Markov, I.L. (2006). Efficient symmetry breaking for boolean satisfiability. IEEE Transactions on Computers, 55(5), 549\u2013558. doi: 10.1109\/TC.2006.75 .","journal-title":"IEEE Transactions on Computers"},{"unstructured":"Audemard, G., & Simon, L. Glucose 4.0 SAT Solver. http:\/\/www.labri.fr\/perso\/lsimon\/glucose\/ .","key":"9244_CR5"},{"doi-asserted-by":"crossref","unstructured":"Babai, L., & Luks, E.M. (1983). Canonical labeling of graphs. In Proceedings of the fifteenth annual ACM symposium on theory of computing (pp. 171\u2013183). ACM.","key":"9244_CR6","DOI":"10.1145\/800061.808746"},{"issue":"2","key":"9244_CR7","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.0.CO;2-U","volume":"23","author":"G Brinkmann","year":"1996","unstructured":"Brinkmann, G. (1996). Fast generation of cubic graphs. Journal of Graph Theory, 23(2), 139\u2013149.","journal-title":"Journal of Graph Theory"},{"issue":"4","key":"9244_CR8","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1002\/jgt.3190090417","volume":"9","author":"R Cameron","year":"1985","unstructured":"Cameron, R., Colbourn, C., Read, R., & Wormald, N.C. (1985). Cataloguing the graphs on 10 vertices. Journal of Graph Theory, 9(4), 551\u2013562.","journal-title":"Journal of Graph Theory"},{"unstructured":"Codish, M., Miller, A., Prosser, P., & Stuckey, P.J. (2013). Breaking symmetries in graph representation. In Rossi, F. (Ed.), Proceedings of the 23rd international joint conference on artificial intelligence, Beijing, China, August 3-9, 2013, IJCAI 2013. IJCAI\/AAAI. http:\/\/www.aaai.org\/ocs\/index.php\/IJCAI\/IJCAI13\/paper\/view\/6480 .","key":"9244_CR9"},{"unstructured":"Codish, M., Miller, A., Prosser, P., & Stuckey, P.J. Constraints for symmetry breaking in graph representation (2014). Full version of [9] (in preparation).","key":"9244_CR10"},{"unstructured":"Crawford, J.M., Ginsberg, M.L., Luks, E.M., & Roy, A. (1996). Symmetry-breaking predicates for search problems. In Aiello, L.C., Doyle, J., & Shapiro, S.C. (Eds.), Proceedings of the fifth international conference on principles of knowledge representation and reasoning (KR\u201996), Cambridge, Massachusetts, USA, November 5-8, 1996 (pp. 148\u2013159). Morgan Kaufmann.","key":"9244_CR11"},{"unstructured":"Faradzev, I. (1978). Constructive enumeration of combinatorial objects. Problmes Combinatoires et Thorie des Graphes Colloque Internat, Paris (pp. 131\u2013135).","key":"9244_CR12"},{"unstructured":"Flener, P., Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., & Walsh, T. (2002). Breaking row and column symmetries in matrix models. In Hentenryck, P.V. (Ed.), Principles and practice of constraint programming - CP 2002, 8th international conference, CP 2002, Ithaca, NY, USA, September 9-13, 2002, proceedings, lecture notes in computer science (Vol. 2470, pp. 462\u2013476). Springer. http:\/\/link.springer.de\/link\/service\/series\/0558\/bibs\/2470\/24700462.htm .","key":"9244_CR13"},{"doi-asserted-by":"crossref","unstructured":"Frisch, A.M., Jefferson, C., & Miguel, I. (2003). Constraints for breaking more row and column symmetries. In Rossi, F. (Ed.), Principles and practice of constraint programming - CP 2003, 9th international conference, CP 2003, Kinsale, Ireland, September 29 - October 3, 2003, Proceedings, lecture notes in computer science (Vol. 2833, pp. 318\u2013332). Springer. doi: 10.1007\/978-3-540-45193-8_22 .","key":"9244_CR14","DOI":"10.1007\/978-3-540-45193-8_22"},{"doi-asserted-by":"crossref","unstructured":"Grayland, A., Miguel, I., & Roney-Dougal, C.M. (2009). Snake lex: An alternative to double lex. In Principles and practice of constraint programming - CP 2009, 15th international conference, CP 2009, Lisbon, Portugal, September 20-24, 2009, Proceedings (pp. 391\u2013399). doi: 10.1007\/978-3-642-04244-7_32 .","key":"9244_CR15","DOI":"10.1007\/978-3-642-04244-7_32"},{"doi-asserted-by":"crossref","unstructured":"Katebi, H., Sakallah, K.A., & Markov, I.L. (2010). Symmetry and satisfiability: An update. In Strichman, O., & Szeider, S. (Eds.), Theory and applications of satisfiability testing - SAT 2010, 13th international conference, SAT 2010, Edinburgh, UK, July 11-14, 2010. Proceedings, lecture notes in computer science (Vol. 6175, pp. 113\u2013127). Springer. doi: 10.1007\/978-3-642-14186-7_11 .","key":"9244_CR16","DOI":"10.1007\/978-3-642-14186-7_11"},{"doi-asserted-by":"crossref","unstructured":"Katebi, H., Sakallah, K.A., & Markov, I.L. (2012). Conflict anticipation in the search for graph automorphisms. In Bj\u00f8rner, N., & Voronkov, A. (Eds.), Logic for programming, artificial intelligence, and reasoning - 18th international conference, LPAR-18, M\u00e9rida, Venezuela, March 11-15, 2012. Proceedings, lecture notes in computer science (Vol. 7180, pp. 243\u2013257). Springer. doi: 10.1007\/978-3-642-28717-6_20 .","key":"9244_CR17","DOI":"10.1007\/978-3-642-28717-6_20"},{"unstructured":"Katebi, H., Sakallah, K.A., & Markov, I.L. (2012). Graph symmetry detection and canonical labeling: Differences and synergies. In Voronkov, A. (Ed.), Turing-100 - The Alan Turing Centenary, Manchester, UK, June 22-25, 2012, EPiC Series (Vol. 10, pp. 181\u2013195). EasyChair. http:\/\/www.easychair.org\/publications\/?page=949492057 .","key":"9244_CR18"},{"doi-asserted-by":"crossref","unstructured":"Katsirelos, G., Narodytska, N., & Walsh, T. (2010). On the complexity and completeness of static constraints for breaking row and column symmetry. In Cohen, D. (Ed.), Principles and practice of constraint programming - CP 2010 - 16th international conference, CP 2010, St. Andrews, Scotland, UK, September 6-10, 2010. Proceedings, lecture notes in computer science (Vol. 6308, pp. 305\u2013320). Springer. doi: 10.1007\/978-3-642-15396-9_26 .","key":"9244_CR19","DOI":"10.1007\/978-3-642-15396-9_26"},{"issue":"1","key":"9244_CR20","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1023\/B:AMAI.0000018578.92398.10","volume":"41","author":"EM Luks","year":"2004","unstructured":"Luks, E.M., & Roy, A. (2004). The complexity of symmetry-breaking formulas. Annals of Mathematics and Artificial Intelligence, 41(1), 19\u201345.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"1","key":"9244_CR21","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0012-365X(97)84782-6","volume":"164","author":"Z Majcher","year":"1997","unstructured":"Majcher, Z., & Michael, J. (1997). Degree sequences of highly irregular graphs. Discrete Mathematics, 164(1), 225\u2013236.","journal-title":"Discrete Mathematics"},{"unstructured":"McKay, B. (1990). nauty user\u2019s guide (version 1.5). Tech. Rep. TR-CS-90-02. Australian National University. Computer Science Department.","key":"9244_CR22"},{"issue":"2","key":"9244_CR23","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1006\/jagm.1997.0898","volume":"26","author":"BD McKay","year":"1998","unstructured":"McKay, B.D. (1998). Isomorph-free exhaustive generation. Journal of Algorithms, 26(2), 306\u2013324.","journal-title":"Journal of Algorithms"},{"issue":"3","key":"9244_CR24","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/jgt.3190190304","volume":"19","author":"BD McKay","year":"1995","unstructured":"McKay, B.D., & Radziszowski, S.P. (1995). R(4, 5) = 25. Journal of Graph Theory, 19(3), 309\u2013322. doi: 10.1002\/jgt.3190190304 .","journal-title":"Journal of Graph Theory"},{"doi-asserted-by":"crossref","unstructured":"McMillan, K.L. (2002). Applying SAT methods in unbounded symbolic model checking. In Brinksma, E., & Larsen, K.G. (Eds.), Computer aided verification, 14th international conference, proceedings, lecture notes in computer science (Vol. 2404, pp. 250\u2013264). Springer. doi: 10.1007\/3-540-45657-0_19 .","key":"9244_CR25","DOI":"10.1007\/3-540-45657-0_19"},{"key":"9244_CR26","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1613\/jair.3809","volume":"46","author":"A Metodi","year":"2013","unstructured":"Metodi, A., Codish, M., & Stuckey, P.J. (2013). Boolean equi-propagation for concise and efficient SAT encodings of combinatorial problems. Journal of Artificial Intelligence Research (JAIR), 46, 303\u2013341.","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"doi-asserted-by":"crossref","unstructured":"Narodytska, N., & Walsh, T. (2013). Breaking symmetry with different orderings. In Principles and practice of constraint programming (pp. 545\u2013561). Springer.","key":"9244_CR27","DOI":"10.1007\/978-3-642-40627-0_41"},{"unstructured":"The on-line encyclopedia of integer sequences. published electronically at http:\/\/oeis.org (2010).","key":"9244_CR28"},{"doi-asserted-by":"crossref","unstructured":"Puget, J. (1993). On the satisfiability of symmetrical constrained satisfaction problems. In Komorowski, H.J., & Ras Z.W. (Eds.), Methodologies for intelligent systems, 7th international symposium, ISMIS \u201993, Trondheim, Norway, June 15-18, 1993, Proceedings, lecture notes in computer science (Vol. 689, pp. 350\u2013361). Springer. doi: 10.1007\/3-540-56804-2_33 .","key":"9244_CR29","DOI":"10.1007\/3-540-56804-2_33"},{"unstructured":"Radziszowski, S.P. (1994). Small Ramsey numbers. Electronic Journal of Combinatorics. http:\/\/www.combinatorics.org\/ . Revision #14: January, 2014.","key":"9244_CR30"},{"key":"9244_CR31","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0167-5060(08)70325-X","volume":"2","author":"RC Read","year":"1978","unstructured":"Read, R.C. (1978). Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations. Ann. Discrete Math, 2, 107\u2013120.","journal-title":"Ann. Discrete Math"},{"doi-asserted-by":"crossref","unstructured":"Read, R.C. (1981). A survey of graph generation techniques. In Combinatorial mathematics VIII (pp. 77\u201389). Springer.","key":"9244_CR32","DOI":"10.1007\/BFb0091809"},{"issue":"12","key":"9244_CR33","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1016\/j.dam.2005.10.018","volume":"155","author":"I Shlyakhter","year":"2007","unstructured":"Shlyakhter, I. (2007). Generating effective symmetry-breaking predicates for search problems. Discrete Applied Mathematics, 155(12), 1539\u20131548. doi: 10.1016\/j.dam.2005.10.018 .","journal-title":"Discrete Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Walsh, T. (2006). General symmetry breaking constraints. In Benhamou, F. (Ed.), Principles and practice of constraint programming - CP 2006, 12th international conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings, lecture notes in computer science (Vol. 4204, pp. 650\u2013664). Springer. doi: 10.1007\/11889205_46 .","key":"9244_CR34","DOI":"10.1007\/11889205_46"},{"unstructured":"Walsh, T. (2012). Symmetry breaking constraints: Recent results. In Hoffmann, J., & Selman, B. (Eds.), Proceedings of the twenty-sixth AAAI conference on artificial intelligence, July 22-26, 2012, Toronto, Ontario, Canada. AAAI Press. http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI12\/paper\/view\/4974 .","key":"9244_CR35"},{"unstructured":"Yip, J., & Hentenryck, P.V. (2011). Symmetry breaking via lexleader feasibility checkers. In Walsh, T. (Ed.), Proceedings of the 22nd international joint conference on artificial intelligence, IJCAI 2011, Barcelona, Catalonia, Spain, July 16-22, 2011 (pp. 687\u2013692). IJCAI\/AAAI. http:\/\/ijcai.org\/papers11\/Papers\/IJCAI11-121.pdf .","key":"9244_CR36"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9244-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-016-9244-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9244-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T01:58:18Z","timestamp":1567735098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-016-9244-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,2]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9244"],"URL":"https:\/\/doi.org\/10.1007\/s10601-016-9244-z","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2016,4,2]]}}}