{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T10:42:39Z","timestamp":1753180959108,"version":"3.41.0"},"reference-count":99,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSF of China","doi-asserted-by":"crossref","award":["61602266 and 61872201"],"award-info":[{"award-number":["61602266 and 61872201"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSFC Research Fellowship for International Young Scientists","award":["11450110409 and 11550110491"],"award-info":[{"award-number":["11450110409 and 11550110491"]}]},{"name":"Science and Technology Development Plan of Tianjin","award":["17JCYBJC15300 and 16JCYBJC41900"],"award-info":[{"award-number":["17JCYBJC15300 and 16JCYBJC41900"]}]},{"name":"Junta de Andaluc\u00eda and the Departmental Research Budget of the Department of Applied Mathematics I of the University of Seville","award":["FQM-016"],"award-info":[{"award-number":["FQM-016"]}]},{"name":"Fundamental Research Funds for the Central Universities and SAFEA: Overseas Young Talents in Cultural and Educational Sector"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>Computing the autotopism group of a partial Latin rectangle (PLR) can be performed in multiple ways. This study has two aims: comparing some of these methods experimentally to identify those that are competitive; and identifying design goals for developing practical software. We compare six families of algorithms (two backtracking and four graph-theoretic methods), with and without using entry invariants (EIs), in a range of settings. Two EIs are considered: frequencies of row, column, and symbol representatives; and 2 \u00d7 2 submatrices. The best approach to computing autotopism groups varies.<\/jats:p>\n          <jats:p>When PLRs have many autotopisms (such as having very few entries or being a group table), the McKay, Meynert, and Myrvold (MMM) method computes generators for the autotopism group efficiently. (The MMM method is the standard way to compute autotopisms.) Otherwise, PLRs ordinarily have trivial or small autotopism groups, and the task is to verify this. The so-called PLR graph method is slightly more efficient in this setting than the MMM method (in some circumstances, around twice as fast).<\/jats:p>\n          <jats:p>With an intermediate number of entries, the quick-to-compute strong EIs are effective at reducing the need for computation without introducing significant overhead. With a full or almost-full PLR, a more sophisticated EI is needed to reduce down-the-line computation.<\/jats:p>\n          <jats:p>These results suggest a hybrid approach to computing autotopism groups: The software decides on suitable EIs based on the input; and the user chooses between the MMM or the PLR graph methods, depending on their dataset.<\/jats:p>\n          <jats:p>\n            This article expands the authors\u2019 previous article\n            <jats:italic>Computing autotopism groups of PLRs: a pilot study<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3412324","type":"journal-article","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T11:13:41Z","timestamp":1601464421000},"page":"1-39","source":"Crossref","is-referenced-by-count":3,"title":["Computing Autotopism Groups of Partial Latin Rectangles"],"prefix":"10.1145","volume":"25","author":[{"given":"Rebecca J.","family":"Stones","sequence":"first","affiliation":[{"name":"Nankai University and Beijing Jiaotong University, Beijing, P. R., China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6474-7301","authenticated-orcid":false,"given":"Ra\u00fal M.","family":"Falc\u00f3n","sequence":"additional","affiliation":[{"name":"Universidad de Sevilla, Seville, Spain"}]},{"given":"Daniel","family":"Kotlar","sequence":"additional","affiliation":[{"name":"Tel-Hai College, Upper Galilee, Israel"}]},{"given":"Trent G.","family":"Marbach","sequence":"additional","affiliation":[{"name":"Ryerson University, China, Toronto, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2001.3177"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2989\/16073606.2018.1502214"},{"key":"e_1_2_1_3_1","first-page":"81","article-title":"A note on the automorphisms of special loops","volume":"8","author":"Artzy Raphael","year":"1954","journal-title":"Riveon Lemat."},{"key":"e_1_2_1_4_1","first-page":"48","article-title":"On uniformly generating Latin squares","volume":"62","author":"Aryapoor Masood","year":"2011","journal-title":"Bull. Inst. Comb. Appl."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-018-0266-x"},{"volume-title":"Proceedings of the 48th ACM Symposium on Theory of Computing. ACM","year":"2016","author":"Babai L\u00e1szl\u00f3","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the International Congress of Mathematicians. World Sci. Publ.","year":"2018","author":"Babai L\u00e1szl\u00f3","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316356"},{"volume-title":"Proceedings of the 24th IEEE Symposium on Foundations of Computer Science. IEEE, 162--171","author":"Babai L\u00e1szl\u00f3","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700017560"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1999.3050"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1963.13.389"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01209171"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2809-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.01.020"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(85)80021-3"},{"volume-title":"Steiner triple systems, and edge-parallelisms.","year":"2015","author":"Cameron Peter C.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-11.3.337"},{"volume-title":"Parallelisms of Complete Designs","author":"Cameron Peter J.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.02.024"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.20282"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2020.111812"},{"volume-title":"Stones","year":"2019","author":"Demirkale Fatih","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"Exact sampling algorithms for Latin squares and sudoku matrices via probabilistic divide-and-conquer","volume":"79","author":"DeSalvo Stephen","year":"2016","journal-title":"Algorithmica"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1997.1624"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Anthony B. Evans. 2018. When Is a Latin Square Based on a Group? Springer International Publishing Cham 41--63.  Anthony B. Evans. 2018. When Is a Latin Square Based on a Group? Springer International Publishing Cham 41--63.","DOI":"10.1007\/978-3-319-94430-2_2"},{"volume-title":"Proceedings of Transgressive Computing 2006: A Conference in Honor of Jean Della Dora. TC2006, 213--230","year":"2006","author":"Falc\u00f3n Ra\u00fal M.","key":"e_1_2_1_28_1"},{"volume-title":"Proceedings of the Spanish Meeting on Computer Algebra and Applications. 95--98","year":"2012","author":"Falc\u00f3n Ra\u00fal M.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","first-page":"239","article-title":"Cycle structures of autotopisms of the Latin squares of order up to 11","volume":"103","author":"Falc\u00f3n Ra\u00fal M.","year":"2012","journal-title":"Ars Combin."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.11.013"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.02.022"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-019-00428-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.05.006"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/mma.4820"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.3390\/sym10080322"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2007.07.004"},{"key":"e_1_2_1_38_1","first-page":"19","article-title":"Partial Latin squares having a Santilli\u2019s autotopism in their autotopism groups","volume":"5","author":"Falc\u00f3n Ra\u00fal M.","year":"2007","journal-title":"J. Dyn. Syst. Geom. Theor."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2015.06.103"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2017.01.002"},{"key":"e_1_2_1_41_1","article-title":"Enumerating partial Latin rectangles","volume":"27","author":"Falc\u00f3n Ra\u00fal M.","year":"2020","journal-title":"Electron. J. Comb."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Wang Fang Rebecca J. Stones Trent G. Marbach Gang Wang and Xiaoguang Liu. 2019. Towards a Latin-square search engine. In Proceedings of the IEEE International Conference on Parallel Distributed Processing with Applications Big Data Cloud Computing Sustainable Computing Communications Social Computing Networking (ISPA\/BDCloud\/SocialCom\/SustainCom\u201919). IEEE 727--735.  Wang Fang Rebecca J. Stones Trent G. Marbach Gang Wang and Xiaoguang Liu. 2019. Towards a Latin-square search engine. In Proceedings of the IEEE International Conference on Parallel Distributed Processing with Applications Big Data Cloud Computing Sustainable Computing Communications Social Computing Networking (ISPA\/BDCloud\/SocialCom\/SustainCom\u201919). IEEE 727--735.","DOI":"10.1109\/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00110"},{"volume-title":"Proceedings of the 5th British Combinatorial Conference. 193--202","author":"Fiorini Stanley","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","unstructured":"Timothy Gowers and Jason Long. 2016. The length of an s-increasing sequence of r-tuples. Retrieved from arXiv:1609.08688 [math.CO].  Timothy Gowers and Jason Long. 2016. The length of an s -increasing sequence of r -tuples. Retrieved from arXiv:1609.08688 [math.CO]."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00018"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (LIPIcs)","volume":"107","author":"Grohe Martin","year":"2018"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0070378"},{"key":"e_1_2_1_48_1","first-page":"201","article-title":"Embedding incomplete Latin rectangles and extending the edge colourings of graphs","volume":"10","author":"Hilton A. J. W.","year":"1977","journal-title":"Nanta Math."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2010-02420-2"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.20151"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6610(1996)4:6<405::AID-JCD3>3.0.CO;2-J"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.13"},{"volume-title":"\u00d6sterg\u00e5rd","year":"2006","author":"Kaski Petteri","key":"e_1_2_1_54_1"},{"volume-title":"Proceedings of the Combinatorics, Graph Theory, Algorithms and Applications Conference. World Science Publishing","year":"1994","author":"Keedwell A. D.","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","first-page":"279","article-title":"Quasigroup automorphisms and symmetric group characters","volume":"51","author":"Kerby Brent","year":"2010","journal-title":"Comment. Math. Univ. Carol."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-10-10473-0"},{"key":"e_1_2_1_58_1","first-page":"689","article-title":"A spectral assignment approach for the graph isomorphism problem","volume":"7","author":"Klus Stefan","year":"2018","journal-title":"Inf. Inference"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(90)90015-O"},{"key":"e_1_2_1_60_1","article-title":"Parity types, cycle structures and autotopisms of Latin squares","volume":"19","author":"Kotlar Daniel","year":"2012","journal-title":"Electron. J. Comb."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2014.05.004"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(79)90018-9"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056498"},{"volume-title":"Proceedings of the Conference on Computational Group Theory. Academic Press","year":"1984","author":"Leon Jeffrey S.","key":"e_1_2_1_64_1"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0062536"},{"volume-title":"Congr. Numer. 30","year":"1981","author":"McKay Brendan D.","key":"e_1_2_1_66_1"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0898"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.20105"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1998.2947"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0261-7"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.21389"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.21515"},{"key":"e_1_2_1_74_1","first-page":"169","article-title":"The classification construction and the non-isomorphism counting of symmetric Latin square","volume":"17","author":"Meng Hui","year":"2008","journal-title":"Adv. Stud. Contemp. Math. (Kyungshang)"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803404"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804331"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.62"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010410"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316338"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850662"},{"volume-title":"Permutation Group Algorithms","author":"Seress \u00c1kos","key":"e_1_2_1_81_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546549"},{"volume-title":"Proceedings of the Conference on Computational Problems in Abstract Algebra. 169--183","year":"1970","author":"Sims Charles C.","key":"e_1_2_1_82_1"},{"volume-title":"Computers in Algebra and Number Theory (Proceedings of the SIAM-AMS Symposium on Applied Mathematics","year":"1971","author":"Sims Charles C.","key":"e_1_2_1_83_1"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.37236\/487"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.02.005"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.20309"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2967758"},{"volume-title":"Marbach","year":"2020","author":"Stones Rebecca J.","key":"e_1_2_1_88_1"},{"key":"e_1_2_1_89_1","first-page":"1","article-title":"A Latin square autotopism secret sharing scheme","volume":"35","author":"Stones Rebecca J.","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"e_1_2_1_90_1","unstructured":"The GAP Group. 2018. GAP\u2014Groups Algorithms Programming\u2014A system for computational discrete algebra. Retrieved from http:\/\/www.gap-system.org\/.  The GAP Group. 2018. GAP\u2014Groups Algorithms Programming\u2014A system for computational discrete algebra. Retrieved from http:\/\/www.gap-system.org\/."},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02941165"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00400-4"},{"key":"e_1_2_1_93_1","article-title":"A generalisation of transversals for Latin squares","volume":"9","author":"Wanless Ian M.","year":"2002","journal-title":"Electron. J. Comb."},{"key":"e_1_2_1_94_1","first-page":"76","article-title":"A partial Latin squares problem posed by","volume":"42","author":"Wanless Ian M.","year":"2004","journal-title":"Blackburn. Bull. Inst. Comb. Appl."},{"volume-title":"Atomic Latin squares based on cyclotomic orthomorphisms. Electron. J. Comb. 12","year":"2005","author":"Wanless Ian M.","key":"e_1_2_1_95_1"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.20045"},{"volume-title":"On Construction and Identification of Graphs","author":"Weisfeiler B.","key":"e_1_2_1_97_1","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0089374"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90009-2"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2920405"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2725272"},{"volume-title":"Two-erasure codes from 3-plexes","author":"Yi Liping","key":"e_1_2_1_101_1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3412324","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3412324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:01Z","timestamp":1750195501000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3412324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":99,"alternative-id":["10.1145\/3412324"],"URL":"https:\/\/doi.org\/10.1145\/3412324","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2020,9,30]]}}}